又是一道卡常题……
思路
YNOI当然要分块啦。
分块之后怎么办？
零散块暴力，整块怎么办？
显然不能暴力改/查询所有的。考虑把相同值的用并查集连在一起，这样修改时就只需要枚举值了。
然而每次修改的\(x\)特别小时仍然复杂度爆炸，发现大于\(x\)的减去\(x\)等价于小于等于\(x\)的加上\(x\)，然后整体减去\(x\)。
那么，设一个块的最大值为\(mx\)，则
- \(2x\geq mx\)时枚举\(x<v\leq mx\)，把\(v\)的并查集连到\(v-x\)上，复杂度\(O(mx-x)\)，\(mx\)变为\(x\)。（即\(mx-=mx-x\)）
- 否则，枚举\(v\leq x\)，把\(v\)的并查集连到\(v+x\)上，然后整体减去\(x\)，复杂度\(O(x)\)，\(mx-=x\)。
你是否发现一件事：在每一块上花\(O(x)\)的时间，就可以使\(mx\)减小\(x\)。也就是说，每一块花费的最多时间是\(O(mx)\)，总共就是\(O(\sqrt m \times mx)\)。
也就是说，这种仿佛暴力的算法，复杂度是正确的。
然而，毒瘤出题人既卡空间，又卡时间，所以要AC还是有些麻烦的。
不过CF上给了\(512MB,3000ms\)，可以去那里。
CF的题似乎被暴力+pragma艹过去了。出题人活该
代码
没怎么卡常的代码，CF上能过：
#include<bits/stdc++.h>
namespace my_std{
using namespace std;
#define pii pair<int,int>
#define fir first
#define sec second
#define MP make_pair
#define rep(i,x,y) for (int i=(x);i<=(y);i++)
#define drep(i,x,y) for (int i=(x);i>=(y);i--)
#define go(x) for (int i=head[x];i;i=edge[i].nxt)
#define sz 100010
#define S 320
typedef long long ll;
typedef double db;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<typename T>inline T rnd(T l,T r) {return uniform_int_distribution<T>(l,r)(rng);}
template<typename T>inline void read(T& t)
{
t=0;char f=0,ch=getchar();double d=0.1;
while(ch>'9'||ch<'0') f|=(ch=='-'),ch=getchar();
while(ch<='9'&&ch>='0') t=t*10+ch-48,ch=getchar();
if(ch=='.'){ch=getchar();while(ch<='9'&&ch>='0') t+=d*(ch^48),d*=0.1,ch=getchar();}
t=(f?-t:t);
}
template<typename T,typename... Args>inline void read(T& t,Args&... args){read(t); read(args...);}
void file()
{
#ifndef ONLINE_JUDGE
freopen("a.txt","r",stdin);
#endif
}
#ifdef mod
ll ksm(ll x,int y){ll ret=1;for (;y;y>>=1,x=x*x%mod) if (y&1) ret=ret*x%mod;return ret;}
ll inv(ll x){return ksm(x,mod-2);}
#else
ll ksm(ll x,int y){ll ret=1;for (;y;y>>=1,x=x*x) if (y&1) ret=ret*x;return ret;}
#endif
// inline ll mul(ll a,ll b){ll d=(ll)(a*(double)b/mod+0.5);ll ret=a*b-d*mod;if (ret<0) ret+=mod;return ret;}
}
using namespace my_std;
int n,m;
int a[sz];
int fa[sz],size[sz];
int getfa(int x){return x==fa[x]?x:fa[x]=getfa(fa[x]);}
int blo,pos[sz];
struct hh
{
int L,R;
int tag,mx;
int f[sz];
int val(int x){return a[getfa(x)]-tag;} // the real value of position x
void rebuild()
{
rep(i,L,R) fa[i]=size[i]=0;
tag=mx=0;
rep(i,L,R)
if (!f[a[i]]) f[a[i]]=fa[i]=i,size[i]=1;
else fa[i]=f[a[i]],++size[fa[i]];
rep(i,L,R) mx=max(mx,a[i]);
}
void modify(int x)
{
if (x>=mx) return;
if (2*x>=mx)
{
rep(i,x+1+tag,mx+tag) if (f[i])
{
int y=i-x;
if (f[y]) fa[f[i]]=f[y],size[f[y]]+=size[f[i]];
else f[y]=f[i],a[f[y]]-=x;
f[i]=0;
}
mx=x;
}
else
{
drep(i,x+tag,1+tag) if (f[i])
{
int y=i+x;
if (f[y]) fa[f[i]]=f[y],size[f[y]]+=size[f[i]];
else f[y]=f[i],a[f[y]]+=x;
f[i]=0;
}
tag+=x;mx-=x;
}
}
int query(int x){return x+tag<sz&&f[x+tag]?size[f[x+tag]]:0;}
}b[S];
void init()
{
blo=sqrt(n);
rep(i,1,n)
{
pos[i]=(i-1)/blo+1;
b[pos[i]].R=i;
if (pos[i]!=pos[i-1]) b[pos[i]].L=i;
}
rep(i,1,pos[n]) b[i].rebuild();
}
int tmp[sz];
void change_(int l,int r,int x)
{
int p=pos[l];
rep(i,b[p].L,b[p].R) b[p].f[a[getfa(i)]]=0;
rep(i,b[p].L,b[p].R) tmp[i]=b[p].val(i);
rep(i,b[p].L,b[p].R) a[i]=tmp[i];
rep(i,l,r) if (a[i]>x) a[i]-=x;
b[p].rebuild();
}
void change(int l,int r,int x)
{
int pl=pos[l],pr=pos[r];
if (pl==pr) return change_(l,r,x);
change_(l,b[pl].R,x),change_(b[pr].L,r,x);
if (pl==pr+1) return;
++pl,--pr;
rep(i,pl,pr) b[i].modify(x);
}
int query_(int l,int r,int x)
{
int ret=0,p=pos[l];
rep(i,l,r)
ret+=(b[p].val(i)==x);
return ret;
}
int query(int l,int r,int x)
{
int pl=pos[l],pr=pos[r];
if (pl==pr) return query_(l,r,x);
int ret=query_(l,b[pl].R,x)+query_(b[pr].L,r,x);
if (pl+1==pr) return ret;
++pl,--pr;
rep(i,pl,pr) ret+=b[i].query(x);
return ret;
}
int main()
{
file();
read(n,m);
rep(i,1,n) read(a[i]);
init();
while (m--)
{
int z,x,l,r;read(z,l,r,x);
if (z==1) change(l,r,x);
else printf("%d\n",query(l,r,x));
}
return 0;
}
卡常之后的代码，洛谷上可以过：
注意：不保证此代码任何时刻都可通过。我是半夜提交的。
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
#include<bits/stdc++.h>
namespace my_std{
using namespace std;
#define rep(i,x,y) for (register int i=x;i<=y;++i)
#define drep(i,x,y) for (register int i=x;i>=y;--i)
#define sz 100010
#define S 320
typedef long long ll;
typedef double db;
char buf[1<<20],*p1=buf,*p2=buf;
inline char getchar(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++;}
inline void read(int& t)
{
t=0;char ch=getchar();
while(ch>'9'||ch<'0') ch=getchar();
while(ch<='9'&&ch>='0') t=t*10+ch-48,ch=getchar();
}
char sr[800000],z[10];int C=-1,Z=0;
inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
void print(register int x)
{
if(x<0)sr[++C]='-',x=-x;
while(z[++Z]=x%10+48,x/=10);
while(sr[++C]=z[Z],--Z);sr[++C]='\n';
}
// void file()
// {
// #ifndef ONLINE_JUDGE
// freopen("a.txt","r",stdin);
// #endif
// }
}
using namespace my_std;
int n,m;
int a[sz];
int fa[sz],size[sz];
int getfa(int x){return x==fa[x]?x:fa[x]=getfa(fa[x]);}
int blo,pos[sz];
struct hh
{
int L,R;
int tag,mx;
int f[sz];
void rebuild()
{
rep(i,L,R) fa[i]=size[i]=0;
tag=mx=0;
rep(i,L,R)
if (!f[a[i]]) f[a[i]]=fa[i]=i,size[i]=1;
else fa[i]=f[a[i]],++size[fa[i]];
rep(i,L,R) mx=max(mx,a[i]);
}
void modify(int x)
{
if (x>=mx) return;
if (2*x>=mx)
{
rep(i,x+1+tag,mx+tag) if (f[i])
{
int y=i-x;
if (f[y]) fa[f[i]]=f[y],size[f[y]]+=size[f[i]];
else f[y]=f[i],a[f[y]]-=x;
f[i]=0;
}
mx=x;
}
else
{
drep(i,x+tag,1+tag) if (f[i])
{
int y=i+x;
if (f[y]) fa[f[i]]=f[y],size[f[y]]+=size[f[i]];
else f[y]=f[i],a[f[y]]+=x;
f[i]=0;
}
tag+=x;mx-=x;
}
}
inline int query(register int x){return x+tag<sz&&f[x+tag]?size[f[x+tag]]:0;}
}b[S];
void init()
{
blo=sqrt(n);
rep(i,1,n) pos[i]=(i-1)/blo+1;
rep(i,1,pos[n]) b[i].L=i*blo-blo+1,b[i].R=min(n,i*blo),b[i].rebuild();
}
int tmp[sz];
void change_(int l,int r,int x)
{
int p=pos[l],tg=b[p].tag;
rep(i,b[p].L,b[p].R) b[p].f[a[getfa(i)]]=0;
rep(i,b[p].L,b[p].R) tmp[i]=a[getfa(i)]-tg;
rep(i,b[p].L,b[p].R) a[i]=tmp[i];
rep(i,l,r) if (a[i]>x) a[i]-=x;
b[p].rebuild();
}
void change(int l,int r,int x)
{
int pl=pos[l],pr=pos[r];
if (pl==pr) return change_(l,r,x);
change_(l,b[pl].R,x),change_(b[pr].L,r,x);
if (pl==pr+1) return;
++pl,--pr;
rep(i,pl,pr) b[i].modify(x);
}
int query_(int l,int r,int x)
{
int ret=0,p=pos[l],X=b[p].tag+x;
rep(i,l,r)
ret+=(a[getfa(i)]==X);
return ret;
}
int query(int l,int r,int x)
{
int pl=pos[l],pr=pos[r];
if (pl==pr) return query_(l,r,x);
int ret=query_(l,b[pl].R,x)+query_(b[pr].L,r,x);
if (pl+1==pr) return ret;
++pl,--pr;
rep(i,pl,pr) ret+=b[i].query(x);
return ret;
}
int main()
{
// file();
// clock_t t=clock();
read(n);read(m);
rep(i,1,n) read(a[i]);
init();
register int z,x,l,r;
rep(_,1,m)
{
read(z);read(l);read(r);read(x);
if (z==1) change(l,r,x);
else print(query(l,r,x));
}
Ot();
// cout<<(clock()-t)/1000.0;
// return 0;
}