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

(Updated: )
oi
, ,

给定一个长度为 $n$ 的整数序列 ${a_i}$，有 $m$ 次操作：

  1. 将区间 $[l,r]$ 加 $v$。
  2. 将区间 $[l,r]$ 每个数对 $v$ 取 $\max$。
  3. 单点查询 $p$ 的值以及其在之前所有操作中一共变化了多少次。

$n\leq 10^5$。

Tutorial

分块，每块内维护其排序，对于整块的 $2$ 操作直接丢到一个递增的 vector 里，Pushdown 时双指针扫描即可。

如果精细一点实现可以做到 $O(N\sqrt N)$，但本人比较懒于是就写了 $O(N\sqrt{N\log N})$。

还可以吉司机线段树，但本人不太会、、分析复杂度。但实测跑得飞快。

Solution(分块)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#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;
}