企业管理专业主要课程_怎么找货源开网店_宁波seo博客_seo自然排名

分块

 之前我们探讨了树状数组和线段树两种数据结构。树状数组基于二进制划分和倍增思想，线段树基于分治思想。它们之所以能够高效地在一个序列上执行指令并统计信息，就是因为他们把序列中的元素聚合成大大小小的“段”，花费额外的代价去对这些段进行维护，从而使得每个区间的信息可以快速地由几个已知的“段”结合而成。
 树状数组也有很多缺点，比如说在维护较为复杂的信息时，比较吃力也正因此我们要学习分块。分块和前面地算法相比效率会低一些，但是更加通用，容易实现。
例题
acwing243.一个简单的整数问题2
把数列分成长度不超过$\lfloor \sqrt{N}\rfloor$的段，其中第i部分地左端点为$(i-1)\ast \lfloor \sqrt{N}\rfloor +1$，右端点为$min(i\lfloor \sqrt{N}\rfloor ,N)$。
预处理数组,sum[i]表示第i段区间的和。add[i]是第i段的增量标记。
对于指令“C l r d”:
1.如果l和r同时处于第i段内，则直接把$A[l],A[l+1],...,A[r]$都加d，同时令$sum[i]+=d\ast (r-l+1)$。
2.否则，设l处于第p段，r处于第q段。
(1)对于$i\in [p+1.q-1]$,令$add[i]+=d$。
(2)对于开头、结尾不足一整段的两部分，按照与第一种情况相同的方法朴素地更新。
对于指令Q l r
1.若l和r同时处于第i段，则$A[l]+A[l+1]+...+A[r]+(r-l+1)\ast add[i]$就是最终答案。
2.否则，设l与r同时处于第p段，r处于第q段，初始化ans=0.
(1)对于$i\in [p+1,q-1],令ans+=sum[i]+add[i]\ast len[i]$,其中len[i]表示第i段地长度。
(2)对于开头结尾不足一整段地两部分，按照与第一种情况相同地方法进行朴素的处理。
时间复杂度$O((N+Q)\ast \sqrt{N})$
分块思想:“大段维护，局部朴素”。

#include <iostream>
#include <math.h>
using namespace std;
typedef long long ll;
#define N 100010
int n, m, t;
ll sum[N];
ll add[N];
int pos[N];
int L[N], R[N];
ll a[N];
void change(int l, int r, int d)
{int p = pos[l], q = pos[r];if (p == q){for (int i = l; i <= r; i ++ ) a[i] += d;sum[p] += (r - l + 1) * d;}else{for (int i = p + 1; i <= q - 1; i ++ ) add[i] += d;for (int i = l; i <= R[p]; i ++ ) a[i] += d;sum[p] += (R[p] - l + 1) * d;for (int i = L[q]; i <= r; i ++ ) a[i] += d;sum[q] += (r - L[q] + 1) * d;}return ;
}
ll ask(int l, int r)
{int p = pos[l], q = pos[r];ll ans = 0;if (p == q){for (int i = l; i <= r; i ++ ) ans += a[i];ans += add[p] * (r - l + 1);}else{for (int i = p + 1; i <= q - 1; i ++ )ans += sum[i] + add[i] * (R[i] - L[i] + 1);for (int i = l; i <= R[p]; i ++ ) ans += a[i];ans += add[p] * (R[p] - l + 1);for (int i = L[q]; i <= r; i ++ ) ans += a[i];ans += add[q] * (r - L[q] + 1);}return ans;
}
int main()
{cin >> n >> m;for (int i = 1; i <= n; i ++ ) scanf("%lld", a + i);t = sqrt(n);for (int i = 1; i <= t; i ++ ){L[i]= (i - 1) * sqrt(n) + 1;R[i] = i * sqrt(n);}if (R[t] < n){t ++ ;L[t] = R[t - 1] + 1;R[t] = n;}for (int i = 1; i <= t; i ++ ){for (int j = L[i]; j <= R[i]; j ++ ){pos[j] = i;sum[i] += a[j];}}while (m -- ){char op[3];int l, r, d;scanf("%s", op);scanf("%d %d", &l, &r);if (*op == 'Q') printf("%lld\n", ask(l, r));else{scanf("%d", &d);change(l, r, d);}}return 0;
}

acwing249.蒲公英
把序列分成T块，每一块的长度L=N/T。对于每一个查询[l,r],设l处于第p块，r处于第q块。把区间分成三部分。
1.开头不足一整段的$[l,L)$。
2.$[p+1,q-1]$块构成的区间$[L,R]$。
3.结尾不足一整段的$(R,r]$。

显然a的众数只可能来自底下两种情况之一。
1.区间$[L,R]$的众数。
2.出现在$[l,L)$与$(R,r]$之间的数。

预处理时，只保留所有以段边界为端点你的区间$[L,R]$的众数。空间复杂度为$O(T^2)$,时间复杂度为$O(NT)$。另外对每个数建立一个STL vector,按顺序保存该数值在序列中的每个出现位置。
对于每个询问，扫描$[l,L)$与$(R,r]$中的每个数，在对应的vector里二分查找即可得到x在$[l,r]$中出现的次数，从而更新答案。时间复杂度为$O(MN/T\ast logN)$。
这个算法的时间复杂度为$O(NT+MN/T\ast logN)$，应取$T=\sqrt{NlogN}$，时间复杂度为$O(N\sqrt{NlogN})$级别。

//Author:XuHt
#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 40006, T = 806;
int a[N], b[N], c[N], L[N], R[N], pos[N], f[T][T];
vector<int> e[N];int find(int x, int l, int r) {return upper_bound(e[x].begin(), e[x].end(), r) - lower_bound(e[x].begin(), e[x].end(), l);
}void work(int x, int l, int r, int &ans, int &cnt) {int w = find(x, l, r);if (w > cnt || (w == cnt && x < ans)) {cnt = w;ans = x;}
}int ask(int l, int r) {int p = pos[l], q = pos[r];int ans = 0, cnt = 0;if (p == q) {for (int i = l; i <= r; i++) work(a[i], l, r, ans, cnt);return b[ans];}int x = 0, y = 0;if (p + 1 <= q - 1) {x = p + 1;y = q - 1;}for (int i = l; i <= R[p]; i++) work(a[i], l, r, ans, cnt);for (int i = L[q]; i <= r; i++) work(a[i], l, r, ans, cnt);if (f[x][y]) work(f[x][y], l, r, ans, cnt);return b[ans];
}int main() {int n, m;cin >> n >> m;for (int i = 1; i <= n; i++) scanf("%d", &a[i]);memcpy(b, a, sizeof(b));sort(b + 1, b + n + 1);int tot = unique(b + 1, b + n + 1) - (b + 1);for (int i = 1; i <= n; i++) {a[i] = lower_bound(b + 1, b + tot + 1, a[i]) - b;e[a[i]].push_back(i);}int t = sqrt(log(n) / log(2) * n);int len = t ? n / t : n;for (int i = 1; i <= t; i++) {L[i] = (i - 1) * len + 1;R[i] = i * len;}if (R[t] < n) {L[t+1] = R[t] + 1;R[++t] = n;}for (int i = 1; i <= t; i++)for (int j = L[i]; j <= R[i]; j++)pos[j] = i;memset(f, 0, sizeof(f));for (int i = 1; i <= t; i++) {memset(c, 0, sizeof(c));int cnt = 0, ans = 0;for (int j = L[i]; j <= n; j++) {if (++c[a[j]] > cnt || (c[a[j]] == cnt && a[j] < ans)) {cnt = c[a[j]];ans = a[j];}f[i][pos[j]] = ans;}}int x = 0;while (m--) {int l, r;scanf("%d %d", &l, &r);l = (l + x - 1) % n + 1;r = (r + x - 1) % n + 1;if (l > r) swap(l, r);x = ask(l, r);printf("%d\n", x);}return 0;
}

acwing250.磁力块
执行一个BFS框架，建立一个队列，追出只包含磁石L，每次从队头取出磁石，把所有能够吸引的磁石加入到队尾。
我们先按照距离进行排序，分成$\sqrt{N}$段，在每一段内部按照质量进行排序。
一定存在一个k，使得：
1.第1到k-1段中的所有磁石质量都不大于H的磁力
2.第k+1段之后的磁石质量都大于H的磁力，不可能被吸引。
1到k-1段符合条件的磁石一定在开头，我们直接在第1到k-1段中，从每段左端开始注意扫描，把能吸引进来的都吸引进来，直到出现第一个不能吸引的磁石（位置P）。之后，把这一段的左端点移动到P的位置。对于每一段来说，上面这个过程的均摊时间复杂度是$O(1)$,处理完这些段的复杂度为$O(\sqrt{N})$。
对于第k段，朴素扫描，时间复杂度为$O(\sqrt{N})$。
整个算法的时间复杂度为$O(N\sqrt{N})$。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e6;
const int w=500;
struct node
{ll d,r;ll m,p;
} a[N];
ll D[N],x0,y_0,now,L[N],R[N],v[N],n,tot,l,r,p,x,y;
queue<ll> q;
bool cmp_d(node a,node b)
{return a.d<b.d;
}
bool cmp_m(node a,node b)
{return a.m<b.m;
}
int main()
{cin>>x0>>y_0>>a[0].p>>a[0].r>>n;a[0].r*=a[0].r;//第一块磁铁for(int i=1;i<=n;i++){cin>>x>>y>>a[i].m>>a[i].p>>a[i].r;a[i].r*=a[i].r;a[i].d=(x0-x)*(x0-x)+(y_0-y)*(y_0-y);//计算距离}sort(a+1,a+1+n,cmp_d);for(ll i=1;i<=n;i+=w){L[++tot]=i;R[tot]=min(n,i+w-1);//计算L和R的范围,也就是第i大块的范围D[tot]=a[R[tot]].d;sort(a+L[tot],a+R[tot]+1,cmp_m);//大块内则排序}q.push(0);ll ans=1;while(q.size()){ll l=q.front();now=a[l].r;p=a[l].p;q.pop();for(ll i=1;i<=tot;i++){if (D[i]>now){for(ll j=L[i];j<=R[i];j++)if (!v[j] && a[j].d<=now && a[j].m<=p)//没有吸过来,而且在范围内{q.push(j);ans++;v[j]=1;}break;}while(L[i]<=R[i] && a[L[i]].m<=p)//加入一块磁铁石,然后把则块磁铁石可以吸收的磁铁石放进去{if (!v[L[i]])//没有被访问{q.push(L[i]);ans++;}++L[i];}}}cout<<ans-1;//不算刚开始的赠送磁石
}

acwing251.小Z的袜子
本题要对询问进行分块，使用莫队算法。
先把所有询问读入，把这些询问按照左端点的值进行递增排序，然后根据左端点的取值进行分块，最多分成$\sqrt{N}$块，每块内部再按照右端点排序。
这样一来，在每一块内，相邻两个询问左端点变化在$\sqrt{N}$以内，右端点变化是单调的。对于左端点来说，整体的时间复杂度为$O(M\sqrt{N})$,对于右端点来说，时间复杂度为$O(N\sqrt{N})$。整体时间复杂度为$((M+N)\ast \sqrt{N})$。
对于每一块询问，先朴素处理该块的第一个询问，得到一个数组num，表示在该块的第一个询问区间$[l,r]$中，颜色为c的袜子有num[c]只。再维护一个变量存储${\sum }_{c}num[c]\ast (num[c]-1)/2$。
然后，我们依次考虑该块的其余询问。当做右端点发生变化时，朴素地在num数组中进行增减，同时更新ans的值。显然，抽到同色袜子的概率就是$ans/C_{r-l+1}^2$。

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
#define N 50010
struct Q{int id;int l, r;
}q[N];
int n, m;
ll tot = 0;
int block, len;
int c[N];
int sum[N];
ll ans[N][2];
int L[N], R[N];
int pos[N];
bool cmp(Q a, Q b)
{if (pos[a.l] != pos[b.l]) return a.l < b.l;return a.r < b.r;
}
void add(int x)
{tot += sum[x];sum[x] += 1;
}
void del(int x)
{sum[x] -= 1;tot -= sum[x];
}
ll gcd(ll a, ll b)
{return b ? gcd(b, a % b) : a;
}
int main()
{cin >> n >> m;for (int i = 1; i <= n; i ++ ) scanf("%d", c + i);for (int i = 1; i <= m; i ++ ){q[i].id = i;scanf("%d%d", &q[i].l, &q[i].r);}block = sqrt(n);len = block;for (int i = 1; i <= len; i ++ ){L[i] = (i - 1) * len + 1;R[i] = i * len;}if (R[len] < m){block += 1;L[block] = R[block - 1] + 1;R[block] = m;}for (int i = 1; i <= block ;i ++ )for (int j = L[i]; j <= R[i]; j ++ )pos[j] = i;sort(q + 1, q + 1 + m, cmp);int l = 1, r = 0;for (int i = 1; i <= m; i ++ ){while (l > q[i].l) add(c[-- l]);while (r < q[i].r) add(c[++ r]);while (l < q[i].l) del(c[l ++]);while (r > q[i].r) del(c[r --]);ans[q[i].id][0] = tot;ans[q[i].id][1] = 1ll * (r - l) * (r - l + 1) / 2;}for (int i = 1; i <= m; i ++ ){if (ans[i][0] == 0) puts("0/1");else{ll t = gcd(ans[i][0], ans[i][1]);ans[i][0] /= t;ans[i][1] /= t;printf("%lld/%lld\n", ans[i][0], ans[i][1]);}}return 0;
}