题解 P4117 【[Ynoi2018]五彩斑斓的世界】
Michael_Bryant · · 个人记录
先推一发我的博客
传送门
这个题是神题
呈现给我们的是两种帅气的区间操作
区间操作我们无非想到线段树 树状数组或者是分块
线段树好像还没见过有关大于某个数的问题
树状数组更别谈了
所以说分块更切实可行
怎么分块呢
block=sqrt(n)
这个自然不用多说
然后对于第一种操作 把所有大于x的数减去x
这个怎么办呢
区间减法打标记
显然不可直接打标记维护
因为你要找的数太tm有特点了
考虑个数据结构
可以把一个块内 值相同的数 连在一起处理
ufs啊对吧
记录每个块内每个数值第一次出现的位置
维护一下每个块内每个数出现次数
修改的时候只需要把对应ufs合并
查询的时候直接查询就成
这是操作1
想一想 时间20s20个点挺虚的
所以我们考虑优化这个修改
怎么优化呢
当我们发现这个区间内的数大于x较多的时候
我们就考虑对于小于x的数做文章
我们把所有小于x的数加上x
然后块内减去x
这样巧妙优化了复杂度
当然了查询就是非常基本的查询
先查两边零散的
再查中间整块的
就搞定了
//我爱真红
//By Michael_Bryant
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
#define M 325
#define N 100005
#define max(a,b) a>b?a:b
#define min(a,b) a<b?a:b
int n,m,f[N],h[M][N],cnt[N],tag[M],v[N],a[N],mx[M];
int block,l[M],r[M],bel[N];
inline char nc()
{
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
char ch=nc();int sum=0,w=1;
while(!(ch>='0'&&ch<='9')) {if(ch=='-') w=-1;ch=nc();}
while(ch>='0'&&ch<='9')sum=sum*10+ch-48,ch=nc();
return sum*w;
}
/*inline int read()
{
int s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
return s*w;
}*/
inline int get(int x)
{
int w,y=x;
while(y^f[y])
{
y=f[y];
}
while(f[x]^y)
{
w=x;
x=f[x];
f[w]=y;
}
return y;
}
inline void getmx(int id)
{
while(!h[id][mx[id]])
{
mx[id]--;
}
}
inline void build(int id)
{
register int i;
for(i=l[id];i<=r[id];++i)
{
a[i]=v[get(i)];
h[id][a[i]]=0;
}
for(i=l[id];i<=r[id];++i)
{
cnt[i]=1;
f[i]=i;
}
for(i=l[id];i<=r[id];++i)
{
if(h[id][a[i]])
{
cnt[h[id][a[i]]]+=cnt[i];
f[i]=h[id][a[i]];
}
else
{
h[id][a[i]]=i;
v[i]=a[i];
}
}
getmx(id);
}
inline void change(int id,int L,int R,int x)
{
register int i,j;
for(i=l[id];i<=r[id];++i)
{
a[i]=v[get(i)];
}
for(i=l[id];i<=r[id];++i)
{
h[id][a[i]]=0;
}
for(i=L;i<=R;++i)
{
if(a[i]-tag[id]>x) a[i]-=x;
}
for(i=l[id];i<=r[id];++i)
{
v[i]=a[i];f[i]=i;
}
build(id);
}
inline void modify(int L,int R,int x)
{
register int i,j;
if(bel[L]==bel[R])
{
change(bel[L],L,R,x);
return;
}
change(bel[L],L,r[bel[L]],x);
change(bel[R],l[bel[R]],R,x);
for(i=bel[L]+1;i<bel[R];++i)
{
if((x<<1)<=mx[i]-tag[i])
{
for(j=tag[i]+1;j<=x+tag[i];++j)
{
if(h[i][j])
{
if(!h[i][j+x])
{
h[i][j+x]=h[i][j];
v[h[i][j]]=x+j;
h[i][j]=0;
}
else
{
cnt[h[i][j+x]]+=cnt[h[i][j]];
f[h[i][j]]=h[i][j+x];
h[i][j]=0;
}
}
}
tag[i]+=x;
}
else
{
for(j=x+tag[i]+1;j<=mx[i];++j)
{
if(h[i][j])
{
if(!h[i][j-x])
{
h[i][j-x]=h[i][j];
v[h[i][j]]=j-x;
h[i][j]=0;
}
else
{
cnt[h[i][j-x]]+=cnt[h[i][j]];
f[h[i][j]]=h[i][j-x];
h[i][j]=0;
}
}
}
getmx(i);
}
}
}
inline int query(int L,int R,int x)
{
int ans=0;
register int i;
if(bel[L]==bel[R])
{
for(i=L;i<=R;++i)
{
if(v[get(i)]-tag[bel[L]]==x)
{
ans++;
}
}
return ans;
}
for(i=L;i<=r[bel[L]];++i)
{
if(v[get(i)]-tag[bel[L]]==x)
{
ans++;
}
}
for(i=l[bel[R]];i<=R;++i)
{
if(v[get(i)]-tag[bel[R]]==x)
{
ans++;
}
}
for(i=bel[L]+1;i<bel[R];++i)
{
if(x+tag[i]<=100000)
{
ans+=cnt[h[i][x+tag[i]]];
}
}
return ans;
}
int main()
{
n=read(),m=read();
block=sqrt(n);
register int i;
for(i=1;i<=n;++i)
{
bel[i]=(i-1)/block+1;
f[i]=i;
}
for(i=1;i<=bel[n];++i)
{
l[i]=(i-1)*block+1;
r[i]=min(i*block,n);
}
for(i=1;i<=n;++i)
{
v[i]=a[i]=read();
mx[bel[i]]=max(a[i],mx[bel[i]]);
}
for(i=1;i<=bel[n];++i)
{
build(i);
}
for(i=1;i<=m;++i)
{
int opt=read(),L=read(),R=read(),x=read();
if(opt==1)
{
modify(L,R,x);
}
else
{
printf("%d\n",query(L,R,x));
}
}
return 0;
}