题目描述
二阶堂真红给了你一个长为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=;char c=getchar();
while(!isdigit(c)){c=getchar();}
while(isdigit(c)){x=(x<<)+(x<<)+(c^);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]=;
int maxn=mn(n,x*n1);
for(R int i=(x-)*n1+;i<=maxn;++i)cnt[i]=,f[i]=i;
for(R int i=(x-)*n1+;i<=maxn;++i){
ma[x]=mx(ma[x],a[i]);
if(!head[x][a[i]])head[x][a[i]]=i,cnt[i]=;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-)*n1+;i<=maxn;++i)a[i]=a[find(i)],head[x][a[i]]=;
for(R int i=(x-)*n1+;i<=maxn;++i)a[i]-=la[x];la[x]=;
}
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]=;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]]=;head[x][pre]=;
}
int main(){
n=rd();m=rd();int opt,l,r,x;n1=sqrt(n);
for(R int i=;i<=n;++i)be[i]=(i-)/n1+,f[i]=i,a[i]=rd();
for(R int i=;i<=be[n];++i)build(i);
while(m--){
opt=rd();l=rd();r=rd();x=rd();
if(opt==){
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]-)*n1+;i<=r;++i)if(a[i]>x)a[i]-=x;
build(be[l]);build(be[r]);
for(int i=be[l]+;i<be[r];++i){
if(ma[i]-la[i]>*x){
for(R int j=la[i]+;j<=la[i]+x;++j)if(head[i][j])upd(i,j,j+x);
la[i]+=x;
}
else{
for(R int j=la[i]++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=;
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]-)*n1+;i<=r;++i)if(a[find(i)]-la[be[r]]==x)ans++;
for(R int i=be[l]+;i<be[r];++i)if(x+la[i]<N)ans+=cnt[head[i][x+la[i]]];
}
printf("%d\n",ans);
}
}
return ;
}