「CSP-J/S2022模拟赛7.12 D」来 / YbtOJ 「分块算法」历史序列

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
using namespace std;
namespace Debug{
	Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
	Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3)+(x<<1)+(c&15),D);x*=f;}
	Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
	Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x+'0'),0):(write(x/10),pc(x%10+'0'),0);}
	Tp I void writeln(Cn Ty& x){write(x),pc('\n');}
}using namespace FastIO;
Cn int N=2e5+10,SS=78,M=N/SS+5;
int n,m,S,L[N],R[N],tot,bl[N],p[N],Ans[N],tAns[M];LL a[N],tg[M];
vector<LL> g[M];
#define pb push_back
I bool cmp(CI x,CI y){return a[x]<a[y];}
I void B(){
	RI i,j;for(S=78,i=1;i<=n;i++) !((i-1)%S)&&(R[tot]=i-1,L[++tot]=i),bl[i]=tot;R[tot]=n;
	for(i=1;i<=n;i++) p[i]=i;for(i=1;i<=tot;i++) sort(p+L[i],p+R[i]+1,cmp);
}
I void PD(CI k){
	if(g[k].empty()) return ;RI i,j,sz=g[k].size();LL mx=g[k].back();
	for(i=L[k],j=0;i<=R[k]&&a[p[i]]<mx;i++){W(j<sz&&a[p[i]]>=g[k][j]) ++j;a[p[i]]=mx,Ans[p[i]]+=sz-j;}g[k].clear();
}
I void BF(CI l,CI r,CI v){RI i,k=bl[l];for(PD(k),i=l;i<=r;i++) a[i]+=v,Ans[i]++;sort(p+L[k],p+R[k]+1,cmp);} 
I void U(CI l,CI r,CI v){
	if(!v) return ;RI i,bL=bl[l],bR=bl[r];if(bL==bR) return BF(l,r,v);
	BF(l,R[bL],v),BF(L[bR],r,v);for(i=bL+1;i<=bR-1;i++) tg[i]+=v,tAns[i]++;
}
I void BE(CI l,CI r,CI v){RI i,k=bl[l];for(PD(k),i=l;i<=r;i++) a[i]+tg[k]<v&&(a[i]=v-tg[k],Ans[i]++);sort(p+L[k],p+R[k]+1,cmp);}
I void E(CI l,CI r,CI v){
	RI i,bL=bl[l],bR=bl[r];if(bL==bR) return BE(l,r,v);
	BE(l,R[bL],v),BE(L[bR],r,v);for(i=bL+1;i<=bR-1;i++) (g[i].empty()||v-tg[i]>g[i].back())&&(g[i].pb(v-tg[i]),0);
}
I LL Qv(CI p){RI k=bl[p];return PD(k),a[p]+tg[k];}
I int Q(CI p){RI k=bl[p];return Ans[p]+tAns[k];}
int main(){
	RI i,o,l,r,v;for(read(n),i=1;i<=n;i++) read(a[i]);
	B();read(m);W(m--) read(o),o==1?read(l,r,v),U(l,r,v):o&1?read(l),write(Qv(l)),pc(' '),writeln(Q(l)):(read(l,r,v),E(l,r,v));
	return 0;
}