题解 P4117 【[Ynoi2018]五彩斑斓的世界】

第二分块，神仙大分块题，不过想清楚了后应该难度相对不太大。 ### Part.1 先看这题的数据范围$a_i\leq 5e5$，想到分块的方式应该与值域有关。另外我们可以发现，我们的值是只减小不增大的，考虑值域上应该有一个均摊，对每块做一个值域，考虑我们可以在这个上面~~搞一些事情~~做一些操作，使复杂度正确。~~然后我就不会了~~ ### Part.2 ~~看了出题人的题解后~~我们可以发现有一个很有意思的trick，我们考虑值域是不增的，所以我们可以让值域最大值与最小值的差值越来越小。 设当前修改操作有一个$x$，当前最大值为$mx$，我们分两种情况讨论。 1. $mx \le x\times 2$ 此时我们把$[x+1,mx]$上的值暴力减。 2. $mx > x\times 2$此时我们把$[1,x]$上的值暴力加，然后打上块整体减的$tag$。 我们每次总是使得块的最大值与最小值越来越近，所以一个块的总复杂的是$O(n)$的，所有块的总复杂度是$O(n\sqrt n)$。 到目前为止，我们解决了最重要的操作。 ### Part.3 但询问时我们每个块如果只记录当前值在块内出现次数的话，很显然是不行的，因为零散块无法快速找到一个下标对应的现在的答案，所以我们考虑让值域的每个值记录她有哪些下标是当前值。或者换句话，对下标来说，就是用一个指针指向她当前在值域上的值。 我们重新定义两个操作。 1. $mx \le x\times 2$ 此时我们把$[x+1,mx]$上的值所包含的下标往$[1,x]$合并。 2. $mx > x\times 2$此时我们把$[1,x]$上的值所包含的下标往$[x+1,x\times 2]$合并，然后打上块整体减的$tag$。 如果是零散块，我们就暴力找出当前下标指向的实际的值，修改后把整个块重构。这样是$O(\sqrt n)$的。 什么样的数据结构能实现这样的操作呢？一个直接的想法就是链表，对每个值维护一个链表，合并是$O(1)$的，满足我们的要求。 然而我们还有一个更高效的数据结构，并查集。我们对每个值维护并查集，合并是$O(1)$的，但在重构块时较链表常数更小，是更优秀的选择。 ### Part.4 说了这么多，我们还是过不了这道题。~~我没有玩你们~~ 仔细观察空间限制，发现是**62.50MB**，~~果然前面还不够dl~~，我们要考虑一种线性空间的做法，其实很简单，有一个trick叫逐块处理，我们发现每个块对总的时间贡献了$O(n+m)$的复杂度，那么我们对每个块跑一遍所有询问就可以了。 那我们其他那么多题为什么没有用这个trick呢？因为用它要满足下面几个性质。 1. 可以离线，显然我们是离线下来对每个块跑询问。 2. 块之间不互相干扰。如果一个块的信息发生改变就要影响相邻或更多的块，那么就不能用。 3. 答案可加性，我们是每次跑询问是把答案加入总答案，如果不可加，那么也不行。 最后告诉你一个好消息，**这个题不卡常！！！**所以~~快乐的~~$code$吧！~~其实就是细节有点多~~ ~~还是贴一下我丑陋的代码吧~~ ```cpp inline int findf(int x) {return x==fa[x]?x:fa[x]=findf(fa[x]);} inline void merge(int u,int v)//合并两个值的下标 { if(rt[v]) fa[rt[u]]=rt[v]; else rt[v]=rt[u],to[rt[v]]=v; siz[v]+=siz[u]; rt[u]=siz[u]=0; } void build(int x)//新建块 { mxval=tag=0; for(int i=L[x];i<=R[x];++i) { mxval=max(mxval,a[i]); if(rt[a[i]]) fa[i]=rt[a[i]]; else rt[a[i]]=fa[i]=i,to[i]=a[i]; ++siz[a[i]]; } } void restruct(int x,int l,int r,int nx)//重构块 { for(int i=L[x];i<=R[x];++i) a[i]=to[findf(i)],rt[a[i]]=siz[a[i]]=0,a[i]-=tag; for(int i=L[x];i<=R[x];++i) to[i]=0; l=max(l,L[x]);r=min(r,R[x]); for(int i=l;i<=r;++i) a[i]=a[i]-(a[i]>nx)*nx; build(x); } void modify(int nx)//修改 { if((nx<<1)<=mxval-tag) { for(int i=tag+1;i<=tag+nx;++i) if(rt[i]) merge(i,i+nx); tag+=nx;//记得修改tag } else { for(int i=tag+nx+1;i<=mxval;++i) if(rt[i]) merge(i,i-nx); if(tag+nx<mxval) mxval=tag+nx;//记得更新最大值 } } void query(int x,int i)//询问 { int l=q[i].l,r=q[i].r,nx=q[i].x; if(nx+tag>5e5) return; if(l<=L[x]&&R[x]<=r) ans[i]+=siz[nx+tag]; else { l=max(L[x],l);r=min(R[x],r); for(int j=l;j<=r;++j) if(to[findf(j)]-tag==nx) ++ans[i]; } } int main() { read(n);read(m); klen=sqrt(n); for(int i=1;i<=n;++i) read(a[i]); for(int i=1;i<=m;++i) read(q[i].opt),read(q[i].l),read(q[i].r),read(q[i].x); blocks=(n-1)/klen+1; for(int i=1;i<=blocks;++i) L[i]=R[i-1]+1,R[i]=i*klen; R[blocks]=n; for(int i=1;i<=blocks;++i)//先枚举块，逐块处理 { memset(rt,0,sizeof(rt)); memset(siz,0,sizeof(siz)); build(i); for(int j=1;j<=m;++j) { if(L[i]>q[j].r||R[i]<q[j].l) continue; else if(q[j].opt==1) { if(q[j].l<=L[i]&&R[i]<=q[j].r) modify(q[j].x); else restruct(i,q[j].l,q[j].r,q[j].x); } else query(i,j); } } for(int i=1;i<=m;++i) if(q[i].opt==2) printf("%d\n",ans[i]); return 0; } ```