P4117 [Ynoi2018] 五彩斑斓的世界
题目大意详细题目传送门
一个长为 \(n\) 的序列 \(a\)，有 \(m\) 次操作
[*]把区间 \(\) 中大于 \(x\) 的数减去 \(x\)。
[*]查询区间 \(\) 中 \(x\) 的出现次数。
\(1\le n\le 10^6\)，\(1\le m\le 5\times 10^5\)，\(0 \le a_i,x \le 10^5+1\)。
注意时限 \(7.5\) 秒且内存限制 \(64MB\)。
思路
一个 Ynoi 神秘套路第二分块（似乎是这个名字）。
发现 \(n\) 很大，如果按询问考虑的话每一次每个块不好处理。于是考虑一个 trick 逐快处理。即将每一个询问离线下来，对于每一个个块去遍历询问按这个询问这个块是整块还是散块查询。于是这个时间复杂度就是 \(O(m\sqrt{n})\) 的可以接受。
之后需要考虑均摊 \(O(1)\) 维护操作。观察到值域不大，这给了我们提示。发现每一次如果维护这个大于\(x\) 的操作就不好做，因为它在每个块内是需要查询不同位置的，如果需要维护则至少要一个 \(V\) 的时间，就无法接受了。
考虑转化。维护每个块的可能最大值 \(k_{\max}\)，考虑两种情况：
[*]当 \(k_{\max}\leq2x\) 时，则这次询问之后将没有元素比 \(x\) 大，于是把所有比 \(x\) 的值全部减 \(x\)，所以此时最大值最多为 \(x\)。
[*]否则我们把所有小于 \(x\) 的值加 \(x\)，然后给这个块打一个 \(x\) 的懒标记，就相当于最大值减了 \(x\)。
这样做的好处是什么呢。发现在这种情况下，最大值和最小值会逐渐接近，在最终重叠的情况下就不变了。这样就不用考虑具体的值，只在值域上维护信息。
具体怎么维护那个减加操作呢，我们需要一个操作是 \(O(1)\) 的东西，然后谁？能想到并查集。
我们开一个值域并查集，然后对于每一次操作，相当于将 \(v\) 指向 \(v\pm x\)，然后 \(v\) 点消失。这样维护的带权并查集没有深度，只在根上进行，所以操作都是 \(O(1)\) 的。但是要注意具体实现时的循环顺序，否则会出现像类似于 01 背包那种多考虑的情况（这是后话）。
上文都是在考虑整块，所以查询就查询并查集维护的那个点即可。考虑如果做散块。
对于散块可以直接重构，因为一个询问最多在两个散块中存在，所以重构也是 \(O(n\sqrt{n})\) 的。具体重构就是我们在并查集合并时也维护一下每一个 \(a_i\) 的最终位置 \(a^{'}_i\)。
这样我们就做到了线性空间和 \(O(n\sqrt{n})\) 的时间内完成了这道题目。
代码
#includeusing namespace std;typedef int ll;const ll MAXN=1e6+10;const ll MAXM=5e5+10;const ll MAXV=2e5+10;ll n,m;ll a;struct Query{ ll op,l,r,x,ans;}q;struct Kuai{ ll l,r,mx,tag;}k;ll f,rt,val,cnt;inline ll find(ll u){ return f==u?u:f=find(f);}inline void merge(ll u,ll v){ if(!rt){ return; } if(rt){ f]=rt; }else{ val]=v; rt=rt; } cnt+=cnt; rt=cnt=0;}inline void init(ll T){ ll l=k.l,r=k.r; for(register int i=l;ix+tag;--i){ merge(i,i-x); } if(mx-tag>x){ mx=x+tag; } }else{ while (!cnt) mx--; for(register int i=tag+1;i>m; for(register int i=1;i>a; } for(register int i=1;i>q.op>>q.l>>q.r>>q.x; } ll kl=sqrt(n); for(register int i=1;i
页:
[1]