首页 > 代码库 > [学习-思考-探究]莫队算法 曼哈顿最小生成树与分块区间询问算法-2
[学习-思考-探究]莫队算法 曼哈顿最小生成树与分块区间询问算法-2
若要转载，不需要联系我，只需要在下面回复一下并注明原文。
在线区间询问算法(增强算法)
考虑保存状态
例题：小Z的袜子
如果对小Z的袜子应用基础算法，会发生什么？
小Z的袜子这道题目，仅仅知道区间[l, r]的答案是不能更新到[l, r+1]的。
为什么？因为还要记录每个区间的状态，也就是每种颜色在区间内出现的次数。
显然我们不能直接把状态保存进每两个端点构成的区间。
两端点构成的区间有n个，一个状态要n个变量，显然空间是不能承受的。（实际上预处理时间也不能承受..）
（当然你可以用之前所述的优化算法来实现..但是略慢一点，后面会一起讲。）
注意到这个状态满足区间可减性。
例如1-10中有5个红色，5个白色
1-5中有2个红色，3个白色。
那么6-10中有3个红色，2个白色。
可以把状态中每一个变量分别相减，也就是状态满足区间可减性。
同理状态也满足区间可加性。
那么我们可以使用前缀和思想，维护序列某一个前缀的状态。为了节省空间，我们只记录了序列最左边的点，到每一个块端点的状态。
具体计算过程，请看以下代码
for (int i = 0; i < n; i++) { insert(tans, tmaxn-2, col[i]); if ((i+1) % block_size == 0) { int b_in = (i+1) / block_size; for (int j = 1; j <= n; j++) { pre[b_in].cnt[j] = st[tmaxn-2].cnt[j]; } } if (i % block_size == 0) { //这个循环的范围仅针对小Z的袜子! int b_in = i / block_size; for (int j = 1; j <= n; j++) { update(tmaxn-2, j); st[b_in].cnt[j] = st[tmaxn-2].cnt[j]; } clear(tmaxn-1); LL ans = 0; for (int j = i; j < n; j++) { insert(ans, tmaxn-1, col[j]); if (j % block_size == 0) { val[b_in][j/block_size] = ans; } } } }
pre就是这个前缀和。同时我们还把任意两个块端点之间的答案存入了val中。
考虑基础算法中的做法，对于询问，我们也从端点开始扩展，不过我们可以利用前缀和恢复状态。显然我们不能把n个变量一一恢复，会超时。
考虑懒惰思想，我们只记录相减的两个前缀的位置，当需要用到某一个变量的时候再更新。
该算法的复杂度是#O(nsqrt{n})#的。如果还没有看懂，可以看以下代码。
#include <iostream> #include <algorithm> #include <cmath> #include <vector> #include <cstdio> using namespace std; //该模版需要状态满足区间可减性 //该模版写的是 小Z的袜子 ... typedef long long LL; const int maxn = 55555; const int tmaxn = 230; const int stat_size = maxn; int block_size; struct stat { int cnt[stat_size]; int ts_sub[stat_size]; int tms_sub, suba, subb; } st[tmaxn], pre[tmaxn]; inline void update(int x, int y) { if (st[x].ts_sub[y] < st[x].tms_sub) { st[x].ts_sub[y] = st[x].tms_sub; if (st[x].suba < 0) { st[x].cnt[y] = 0; } else st[x].cnt[y] = st[st[x].suba].cnt[y]-pre[st[x].subb].cnt[y]; } } inline void sub(int x, int a, int b) { st[x].suba = a; st[x].subb = b; st[x].tms_sub ++; } inline void clear(int x) { sub(x, -1, -1); } inline void insert(LL &o, int x, int c) { update(x, c); //这里是小z的袜子独有写法 o -= (((LL)st[x].cnt[c])*(st[x].cnt[c]-1)) >> 1; st[x].cnt[c] ++; o += (((LL)st[x].cnt[c])*(st[x].cnt[c]-1)) >> 1; } LL val[tmaxn][tmaxn]; int col[maxn]; int n, m; vector<int> ra, rb; inline LL getAns(int l, int r) { int tmp_in = tmaxn-1; if (r-l+1 <= block_size) { clear(tmp_in); LL ret = 0; for (int i = l; i <= r; i++) { insert(ret, tmp_in, col[i]); } return ret; } else { int a = l, b = r; ra.clear(), rb.clear(); while (a % block_size) { ra.push_back(a); a++; } while (b % block_size) { rb.push_back(b); b--; } int a_b = a / block_size; int b_b = b / block_size; LL ret = val[a_b][b_b]; sub(tmp_in, b_b, a_b); for (int i = 0; i < ra.size(); i++) { insert(ret, tmp_in, col[ra[i]]); } for (int i = 0; i < rb.size(); i++) { insert(ret, tmp_in, col[rb[i]]); } return ret; } } LL gcd(LL a, LL b) { if (!b) return a; return gcd(b, a%b); } int main() { //freopen("sock.in", "r", stdin); //freopen("sock.out", "w", stdout); scanf("%d%d", &n, &m); for (int i = 0; i < n; i++) { scanf("%d", &col[i]); } block_size = sqrt(n); LL tans = 0; for (int i = 0; i < n; i++) { insert(tans, tmaxn-2, col[i]); if ((i+1) % block_size == 0) { int b_in = (i+1) / block_size; for (int j = 1; j <= n; j++) { pre[b_in].cnt[j] = st[tmaxn-2].cnt[j]; } } if (i % block_size == 0) { //这个循环的范围仅针对小Z的袜子! int b_in = i / block_size; for (int j = 1; j <= n; j++) { update(tmaxn-2, j); st[b_in].cnt[j] = st[tmaxn-2].cnt[j]; } clear(tmaxn-1); LL ans = 0; for (int j = i; j < n; j++) { insert(ans, tmaxn-1, col[j]); if (j % block_size == 0) { val[b_in][j/block_size] = ans; } } } } for (int i = 1; i <= m; i++) { int l, r; scanf("%d%d", &l, &r); LL ans = getAns(l-1, r-1); LL len = r-l+1; if (ans == 0) { printf("0/1\n"); } else { LL fm = len*(len-1)/2; LL g = gcd(ans, fm); printf("%lld/%lld\n", ans/g, fm/g); } } return 0; }
[学习-思考-探究]莫队算法 曼哈顿最小生成树与分块区间询问算法-2
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。