终于有时间做这道题了。
五彩斑斓的世界(第二分块)
听说是大分块中最简单的，于是来做做。
题意：
给定长为 \(n\) 的序列和 \(m\) 次操作。
操作 1 为把区间 \([l,r]\) 所有大于等于 \(x\) 的数减去 \(x\)。
操作 2 为查询 \([l,r]\) 内值为 \(x\) 的数的个数。
\(n\leq 10^6\)，\(m \leq 5\times 10^5\)，\(V \leq 10^5+1\)。
7.5s，64MB。
Part 1
先考虑操作 1。
只有减操作，先势能分析一下。
手玩一下分析性质。
设当前最大值为 \(mx\)。
如果 \(mx \geq 2x\)，那么操作后必然 \(mx=mx-x\)。
否则对于 \(mx < 2x\)，操作后最坏情况 \(mx=x\)。
然后不难想到对两种情况如此维护：
- 对于 \(mx \geq 2x\)，枚举值域 \([0,x]\)，把贡献合并到 \([0+x,x+x]\)，并打上区间 \(-x\) 的标记。
- 对于 \(mx < 2x\)，枚举值域 \((x,mx]\)，把贡献合并到 \((x-x,mx-x]\)。
显然枚举和值域的减少是同阶的。
由于还有操作 2 的区间查询，所以考虑分块（都是大分块系列了，难道不先考虑分块？）。
那么每一块值域为 \(V\)，总值域 \(O(V\sqrt n)\)。
怎么维护呢？
Part 2
由于算法标签上有并查集所以嘛。
确实可以用并查集。
对于每一块，考虑维护值 \(i\) 的并查集，出现次数就是当前并查集的 size。合并贡献平凡。
对于边角块，就要暴力重构。
为了保证暴力重构的复杂度，可以用形如 "动态开点并查集" 的方式维护。
大概是维护这么几个东西：
\(rt_i\)：值 \(i\) 的根。
\(sz_i\)：值 \(i\) 的大小。
\(val_i\)：根为 \(i\) 的值。
\(fa_i\)：\(i\) 位置的 \(fa\)。
Part 3
目前已经可以过弱化版 Welcome home, Chtholly。
由于此题空间限制为 64MB ...，显然不能每一块分别开一个并查集。
然后我就不会惹。。。
看了下题解。
原来还可以利用这题不强制在线。
把询问离线，对于每一块分别做一次，分别算贡献即可。
卡常也不难。还是老朋友 c++98 register 和 inline。
#include<bits/stdc++.h>
#define re register
using namespace std;
const int N=1e6+5,M=5e5+5,T=1000;
int n,m,V,L,R,a[N];
int mx,tag,fa[N],rt[N],sz[N],val[N],ans[M];
struct node{int op,l,r,x;} q[M];
int find(int x) {return x==fa[x]?x:fa[x]=find(fa[x]);}
char buf[1<<15],*p1=buf,*p2=buf;
#define nc() (p1==p2&&(p2=buf+fread(p1=buf,1,1<<15,stdin),p1==p2)?-1:*p1++)
inline int rd()
{
int x=0;char c=nc();
for(;!isdigit(c);c=nc());
for(; isdigit(c);c=nc()) x=(x<<3)+(x<<1)+(c^48);
return x;
}
inline void merge(int x,int y)
{
if(!rt[y]) val[rt[y]=rt[x]]=y;
else fa[rt[x]]=rt[y];
sz[y]+=sz[x];
sz[x]=rt[x]=0;
}
inline void clear(int l=L,int r=R)
{
for(re int i=l;i<=r;i++)
{
a[i]=val[find(i)];
sz[a[i]]=rt[a[i]]=0;
a[i]-=tag;
}
tag=0;
for(re int i=l;i<=r;i++) fa[i]=0;
}
inline void build(int l=L,int r=R)
{
mx=0;
for(re int i=l;i<=r;i++)
{
if(!rt[a[i]]) rt[a[i]]=i,fa[i]=i,val[i]=a[i];
else fa[i]=rt[a[i]];
sz[a[i]]++;
mx=max(mx,a[i]);
}
}
inline void rebuild(int l,int r,int x)
{
clear();
for(re int i=l;i<=r;i++) if(a[i]>x) a[i]-=x;
build();
}
inline void modify(int x)
{
if(mx-tag<2*x) {for(re int i=tag+x+1;i<=mx;i++) if(rt[i]) merge(i,i-x);mx=min(mx,tag+x);}
else {for(re int i=tag;i<=tag+x;i++) if(rt[i]) merge(i,i+x);tag+=x;}
}
int main()
{
n=rd(),m=rd();
for(re int i=1;i<=n;i++) V=max(V,a[i]=rd());
for(re int i=1;i<=m;i++) q[i].op=rd(),q[i].l=rd(),q[i].r=rd(),q[i].x=rd();
for(re int i=0;i<=n/T;i++)
{
L=max(1,i*T),R=min(n,i*T+T-1);
build();
for(re int j=1;j<=m;j++)
{
int op=q[j].op,l=q[j].l,r=q[j].r,x=q[j].x;
if(R<l||r<L) continue;
if(l<=L&&R<=r)
{
if(op==1) modify(x);
else if(x+tag<=V) ans[j]+=sz[x+tag];
}
else
{
l=max(l,L),r=min(r,R);
if(op==1) rebuild(l,r,x);
else for(int k=l;k<=r;k++) if(tag+x==val[find(k)]) ans[j]++;
}
}
clear();
}
for(re int i=1;i<=m;i++) if(q[i].op==2) printf("%d\n",ans[i]);
}