第二分块
题意：给出一个序列 \(a_{1...n}\)，有 \(m\) 次操作。每次：
-
修改：给出 \(l,r,x\)，表示把区间 \([l,r]\) 中 \(>x\) 的数减去 \(x\)
-
查询：给出 \(l,r,x\)，求 \([l,r]\) 中有多少个数 \(=x\)
\(1\le n\le 10^6,\space 1\le m\le 5\times 10^5,\space 0\le a_i,x\le 10^5+1\)，时间限制 \(7.5\text{s}\)，空间限制 \(64\text{MB}\)
考虑分块，块长为 \(B\)。
发现值域只有 \(0...10^5+1\)，我们需要从这方面入手。
考虑整块的操作，每个块维护 \(t_x\) 表示初始为 \(x\) 的数值在操作后变成的数，以及 \(s_x\) 表示当前 \(=x\) 的数字个数。
设块内数字最大值为 \(mx\)，减去的数为 \(x\)，分类讨论：
-
\(x\ge\dfrac {mx}2\)：每个数减一次之后一定 \(\le x\)，值域上遍历一下 \(x+1...mx\)，更新这些值的 \(t\)。
-
\(x<\dfrac {mx}2\)：此时如果更新 \(t\) 会发现无法处理。考虑让 \(\le x\) 的数加上 \(x\)，然后打个整体减 \(x\) 标记。
对于散块的操作，暴力更新块内值，然后重新初始化 \(t\) 和 \(s\)。
发现初始化难搞，我们可以把 \(t\) 数组映射到块内元素上。具体的，设 \(r_x\) 表示块内第一个 \(=x\) 的数出现位置，设 \(t_i\) 表示 \(a_i\) 当前的值为 \(a_{t_i}\)。
用并查集维护 \(t\)。对于根 \(i\)，因为 \(t_i=i\) 不能递归，维护 \(v_i\) 表示这个根的数值即可。
但是空间是 \(O(\dfrac {n^2}B)\) 的，无法通过。考虑一个 trick，因为每个块是独立的，所以可以在最外层枚举块，然后依次扫描每个操作。
点击查看代码
#include<bits/stdc++.h>
#define ll int
#define ull unsigned ll
#define mkp make_pair
#define fi first
#define se second
#define pir pair<ll,ll>
#define pb push_back
using namespace std;
const ll maxn=1e6+10;
ll B=1000,op[maxn][4],L,R,mx,tag;
ll n,m,a[maxn],d[maxn],rt[maxn],val[maxn],siz[maxn],ans[maxn],o[maxn],g;
inline ll find(ll x){
ll &dx=d[x];
return x==dx? x:dx=find(dx);
}
inline void merg(const ll &x,const ll &y){
ll &rx=rt[x], &ry=rt[y];
if(ry) d[rx]=ry;
else{
ry=rx;
val[ry]=y;
}
siz[y]+=siz[x], rx=siz[x]=0;
}
inline void build(){
mx=tag=0;
for(register ll i=L;i<=R;++i){
ll ai=a[i];
mx=max(mx,ai);
if(rt[ai]) d[i]=rt[ai];
else rt[ai]=d[i]=i, val[i]=ai;
++siz[ai];
}
}
inline void block_change(const ll &x){
if(mx-tag>2*x){
for(register ll i=tag+1;i<=tag+x;++i)
merg(i,i+x);
tag+=x;
} else{
for(register ll i=tag+x+1;i<=mx;++i)
merg(i,i-x);
mx=min(mx,tag+x);
}
}
inline void clr(){
for(ll i=L;i<=R;++i){
a[i]=val[find(i)];
rt[a[i]]=siz[a[i]]=0;
a[i]-=tag;
}
for(ll i=L;i<=R;i++) val[i]=d[i]=0;
}
inline void part_change(const ll &l,const ll &r,const ll &x){
for(ll i=L;i<=R;++i){
a[i]=val[find(i)];
rt[a[i]]=siz[a[i]]=0;
a[i]-=tag;
}
for(ll i=L;i<=R;i++) val[i]=d[i]=0;
for(ll i=l;i<=r;++i)
if(a[i]>x) a[i]-=x;
mx=tag=0;
for(register ll i=L;i<=R;++i){
ll ai=a[i];
mx=max(mx,ai);
if(rt[ai]) d[i]=rt[ai];
else rt[ai]=d[i]=i, val[i]=ai;
++siz[ai];
}
}
inline void query(const ll &l,const ll &r,const ll &x,ll &res){
if(l==L&&r==R){
if(x+tag<=1e5+1) res+=siz[x+tag]; return;
}
for(ll i=l;i<=r;++i)
if(val[find(i)]-tag==x) ++res;
}
inline void rd(ll &x){
char c;
while(!isdigit(c=getchar())) ;
x=c-'0';
while(isdigit(c=getchar())) x=x*10+c-'0';
}
int main(){
rd(n), rd(m); B=sqrt(n);
for(register ll i=1;i<=n;++i) rd(a[i]);
for(register ll i=1;i<=m;++i){
rd(op[i][0]), rd(op[i][1]), rd(op[i][2]), rd(op[i][3]);
}
ll o=0;
while(o<n){
L=o+1, R=min(n,o+=B);
build();
for(ll j=1;j<=m;++j){
ll t=op[j][0], l=op[j][1], r=op[j][2], x=op[j][3];
if(t==1){
if(x==0||r<L||l>R) continue;
if(l<=L&&R<=r){
block_change(x);
} else{
part_change(max(l,L),min(r,R),x);
}
}
else query(max(l,L),min(r,R),x,ans[j]);
}
clr();
}
for(register ll i=1;i<=m;i++)
if(op[i][0]==2) printf("%d\n",ans[i]);
return 0;
}