题目描述
二阶堂真红给了你一个长为n的序列a，有m次操作
1.把区间[l,r]中大于x的数减去x
2.查询区间[l,r]中x的出现次数
题解
做YNOI真**爽。。。
我们发现这道题的操作非常诡异，把大于x的数减去x。
想一想这个操作会带来什么，会使这个数列的极差减小x(如果有大于x的数的话)。
然后如果我们能以至多O(x)的代价是极差缩小x的话，那么它的总复杂度是不会超过O(n)的。
然后我们发现log数据结构没法维护这种东西。
于是就用到了分块，每个块中维护每种数字出现的最早位置，然后把相同的数用并查集并起来。
对于修改操作。
我们讨论一下，x-0和maxnum-x哪个大，x-0大的话，就把小于x的数加上x,并且打个标记。
否则就把大于x的减掉x，这个用并查集搞就好了。
边角直接暴力就好了，注意每次暴力之前要把所有数都搞成当前数字的值。
注意数组越界。。。
代码
#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize ("Ofast") #pragma GCC optimize ("Ofast","inline","unroll-loops") #pragma GCC optimize ("no-stack-protector") #include<cstdio> #include<vector> #include<cmath> #include<cctype> #define R register #define N 100009 #define M 318 using namespace std; typedef long long ll; int n,m,n1,f[N],head[M][N],a[N],be[N],ma[M],la[M],cnt[N]; inline int rd(){ int x=0;char c=getchar(); while(!isdigit(c)){c=getchar();} while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();} return x; } int find(int x){return f[x]=f[x]==x?x:find(f[x]);} inline int mn(const int &x,const int &y){ return x>y?y:x; } inline int mx(const int &x,const int &y){ return x>y?x:y; } inline void build(const int &x){ ma[x]=0; int maxn=mn(n,x*n1); for(R int i=(x-1)*n1+1;i<=maxn;++i)cnt[i]=0,f[i]=i; for(R int i=(x-1)*n1+1;i<=maxn;++i){ ma[x]=mx(ma[x],a[i]); if(!head[x][a[i]])head[x][a[i]]=i,cnt[i]=1;else{f[i]=head[x][a[i]];cnt[head[x][a[i]]]++;} } } inline void pushdown(const int &x){ int maxn=mn(n,x*n1); for(R int i=(x-1)*n1+1;i<=maxn;++i)a[i]=a[find(i)],head[x][a[i]]=0; for(R int i=(x-1)*n1+1;i<=maxn;++i)a[i]-=la[x];la[x]=0; } inline void upd(const int &x,const int &pre,const int &now){ ma[x]=mx(ma[x],now); if(!head[x][now]){ head[x][now]=head[x][pre];head[x][pre]=0;a[head[x][now]]=now; return; } f[head[x][pre]]=head[x][now];cnt[head[x][now]]+=cnt[head[x][pre]];cnt[head[x][pre]]=0;head[x][pre]=0; } int main(){ n=rd();m=rd();int opt,l,r,x;n1=sqrt(n); for(R int i=1;i<=n;++i)be[i]=(i-1)/n1+1,f[i]=i,a[i]=rd(); for(R int i=1;i<=be[n];++i)build(i); while(m--){ opt=rd();l=rd();r=rd();x=rd(); if(opt==1){ if(be[l]==be[r]){ pushdown(be[l]); for(R int i=l;i<=r;++i)if(a[i]>x)a[i]-=x; build(be[l]); } else{ pushdown(be[l]);pushdown(be[r]); for(R int i=l;i<=be[l]*n1;++i)if(a[i]>x)a[i]-=x; for(R int i=(be[r]-1)*n1+1;i<=r;++i)if(a[i]>x)a[i]-=x; build(be[l]);build(be[r]); for(int i=be[l]+1;i<be[r];++i){ if(ma[i]-la[i]>2*x){ for(R int j=la[i]+1;j<=la[i]+x;++j)if(head[i][j])upd(i,j,j+x); la[i]+=x; } else{ for(R int j=la[i]+1+x;j<=ma[i];++j)if(head[i][j])upd(i,j,j-x); ma[i]=mn(ma[i],la[i]+x); } } } } else{ int ans=0; if(be[l]==be[r]){ for(R int i=l;i<=r;++i)if(a[find(i)]-la[be[l]]==x)ans++; } else{ for(R int i=l;i<=be[l]*n1;++i)if(a[find(i)]-la[be[l]]==x)ans++; for(R int i=(be[r]-1)*n1+1;i<=r;++i)if(a[find(i)]-la[be[r]]==x)ans++; for(R int i=be[l]+1;i<be[r];++i)if(x+la[i]<N)ans+=cnt[head[i][x+la[i]]]; } printf("%d ",ans); } } return 0; }