首页 > 代码库 > Codeforces 551E GukiZ and GukiZiana（分块思想）
Codeforces 551E GukiZ and GukiZiana（分块思想）
题目链接 GukiZ and GukiZiana
题目大意：一个数列，支持两个操作。一种是对区间$[l, r]$中的数全部加上$k$，另一种是查询数列中值为$x$的下标的最大值减最小值。
$n <= 500000, q <= 50000$
我一开始的反应是线段树，然后发现自己完全想错了……
这道题时限10秒，但也很容易超时。我后来是用分块过的。
把序列分成$\sqrt{n}$个块，每个块的大小为$\sqrt{n}$（最后一个块可能因为不能整除的关系可能会小一些）
每个块维护一个值$delta[i]$，表示这块的每一个数值都要加上这个值。
第1种操作的时候，找到$l$和$r$所在的块。
这两个块之间（不包含$l$所在的块和$r$所在的块，如果没有就不修改）的所有块的$delta$都加上$x$
这样就降低了修改的时间复杂度
$l$所在的块中的元素依次遍历，若下标满足$l <= i <= r$，则值加$x$
$r$所在的块中的元素依次遍历，若下标满足$l <= i <= r$，则值加$x$
每个块内按照值升序排序（第二关键字为下标）
当一个块的整体大小顺序可能发生改变时，就对这个块内部sort一遍，当然没必要sort的时候不要sort
不然可能TLE
查询的时候对每个块二分查找，找到值为$x$的元素的下标，并实时更新答案。
时间复杂度$O(q\sqrt{n}log(\sqrt{n}))$
#include <bits/stdc++.h>using namespace std;#define rep(i, a, b) for (int i(a); i <= (b); ++i)#define dec(i, a, b) for (int i(a); i >= (b); --i)#define fi first#define se secondtypedef long long LL;const int N = 500010;const int Q = 810;int block_size, block_num, n, q, c[N], cnt, et, op, l, r;LL a[N], delta[N], x;vector <pair<LL, int> > block[Q];void update(int l, int r, LL x){ rep(i, c[l] + 1, c[r] - 1) delta[i] += x; for (auto &node : block[c[l]]) if (node.se >= l && node.se <= r) node.fi += x; sort(block[c[l]].begin(), block[c[l]].end()); if (c[r] > c[l]){ for (auto &node : block[c[r]]) if (node.se >= l && node.se <= r) node.fi += x; sort(block[c[r]].begin(), block[c[r]].end()); }}void query(LL x){ int L = 1 << 30, R = -1; rep(i, 1, block_num){ auto it = lower_bound(block[i].begin(), block[i].end(), make_pair(x - delta[i], 0)); if (it != block[i].end() && it -> first == x - delta[i]) L = min(L, it -> se); it = lower_bound(block[i].begin(), block[i].end(), make_pair(x - delta[i] + 1, 0)); if (it != block[i].begin()){ --it; if (it -> fi == x - delta[i]) R = max(R, it -> se); } } if (~R) printf("%d\n", R - L); else puts("-1");}int main(){ scanf("%d%d", &n, &q); rep(i, 1, n) scanf("%lld", a + i); block_size = sqrt(n + 0.5); block_num = n / block_size; if (n % block_size) ++block_num; cnt = 1; rep(i, 1, n){ ++et; c[i] = cnt; block[cnt].push_back({a[i], i}); if (et == block_size){ et = 0; ++cnt; } } rep(i, 1, block_num) sort(block[i].begin(), block[i].end()); for (; q--; ){ scanf("%d", &op); if (op == 1){ scanf("%d%d%lld", &l, &r, &x); update(l, r, x); } else{ scanf("%lld", &x); query(x); } } return 0;}
Codeforces 551E GukiZ and GukiZiana（分块思想）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。