「CSP-J/S2022模拟赛7.12 D」来 / YbtOJ 「分块算法」历史序列
给定一个长度为 n 的整数序列 {a_i}，有 m 次操作：
- 将区间 [l,r] 加 v。
- 将区间 [l,r] 每个数对 v 取 max。
- 单点查询 p 的值以及其在之前所有操作中一共变化了多少次。
nleq 10^5。
Tutorial
分块，每块内维护其排序，对于整块的 2 操作直接丢到一个递增的 vector 里，Pushdown 时双指针扫描即可。
如果精细一点实现可以做到 O(Nsqrt N)，但本人比较懒于是就写了 O(Nsqrt{Nlog N})。
还可以吉司机线段树，但本人不太会、、分析复杂度。但实测跑得飞快。
Solution(分块)
代码语言：javascript复制#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 '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;
}
