第七个点wrong answer 8032nd numbers differ - expected: '0', found: '316'
调了一天了QAQ
#include<iostream>
#include<cmath>
using namespace std;
inline int read(){
int res=0,in=getchar();
while(in<'0'||in>'9')in=getchar();
while(in>='0'&&in<='9')res=(res<<1)+(res<<3)+(in^48),in=getchar();
return res;
}
const int N=100100,S=333;
int n,m,k,siz,bel[N],nam[S][N],col[N*S],fa[N*S],laz[S],cnt[N*S],mx[S];
int find(int id){return fa[id]=(fa[id]==id?id:find(fa[id]));}
inline void insert(int id,int i){
cnt[id]++;
fa[i]=id;
}
inline void erase(int i){
cnt[find(i)]--;
fa[i]=0;
}
inline int getName(int blk,int x){
if(!nam[blk][x])nam[blk][x]=++k,col[k]=x,fa[k]=k;
return nam[blk][x];
}
inline int move(int&fro,int&to){
if(to)fa[fro]=to,cnt[to]+=cnt[fro],cnt[fro]=0;
else to=fro;
}
void init(){
cin>>n>>m;
siz=(int)sqrt(n);
k=n;
for(int i=1;i<=n;i++){
int x=read();
bel[i]=(i-1)/siz+1;
mx[bel[i]]=max(mx[bel[i]],x);
insert(getName(bel[i],x),i);
}
}
void update(int l,int r,int x){
for(int i=l;i<=min(bel[l]*siz,r);i++)
if(col[find(i)]-laz[bel[i]]>x){
int num=col[find(i)];
erase(i);
insert(getName(bel[i],num-x),i);
}
if(bel[l]!=bel[r])
for(int i=bel[r]*siz-siz+1;i<=r;i++)
if(col[find(i)]-laz[bel[i]]>x){
int num=col[find(i)];
erase(i);
insert(getName(bel[i],num-x),i);
}
for(int i=bel[l]+1;i<bel[r];i++)
if(mx[i]-laz[i]>x){
if(mx[i]-laz[i]<=x*2){
for(int j=x+laz[i]+1;j<=mx[i];j++){
move(nam[i][j],nam[i][j-x]);
col[nam[i][j-x]]=j-x;
nam[i][j]=0;
}
for(mx[i]=x+laz[i];!nam[i][mx[i]];mx[i]--);
}
else{
for(int j=laz[i]+1;j<=x+laz[i];j++){
move(nam[i][j],nam[i][j+x]);
col[nam[i][j+x]]=j+x;
nam[i][j]=0;
}
laz[i]+=x;
}
}
}
int get(int l,int r,int x){
int res=0;
// for(int i=1;i<=n;i++)cout<<col[find(i)]<<' '<<laz[bel[i]]<<" ";cout<<endl;
// cout<<l<<' '<<r<<' '<<x<<endl;
for(int i=l;i<=min(r,bel[l]*siz);i++)res+=(col[find(i)]-laz[bel[i]]==x);
if(bel[l]!=bel[r])
for(int i=bel[r]*siz-siz+1;i<=r;i++)res+=(col[find(i)]-laz[bel[i]]==x);
for(int i=bel[l]+1;i<bel[r];i++)res+=cnt[nam[i][x+laz[i]]];
return res;
}
int main(){
// freopen("E://read.txt","r",stdin);
init();
while(m--){
// for(int i=1;i<=n;i++)cout<<col[find(i)]-laz[bel[i]]<<' ';cout<<endl;
int opt=read(),l=read(),r=read(),x=read();
if(opt==1)update(l,r,x);
else printf("%d\n",get(l,r,x));
}
return 0;
}