「CSP-J/S2022模拟赛7.8 D」平凡的我

(Updated: )
oi
, , ,

给定一个长度为 $N$ 的数组 $A$，$Q$ 次操作：

  1. 单点修改 $A_p = v$。
  2. 查询 $a[l] + a[l+1] + \cdots a[r]$ 的历史最小值。

$N,Q\leq 1.2\times 10^5$。

Tutorial(K-D Tree / 四分树)

考虑建立以 $l,r$ 为两轴的平面以维护答案。

查询即为查询该平面上的一点的权值。

修改操作即修改满足 $l\leq p \leq r$ 的所有 $[l,r]$ 点的权值，显然这是一个矩形。

那么我们就变成了矩阵修改，单点查询问题。

每个点维护当前值以及最小值，用 K-D Tree / 四分树 维护即可。

时间复杂度：$O(N\sqrt N)$。

Tutorial(莫队 + 线段树)

把所有操作离线。

考虑每个操作添加“时间戳”关键字。

那么我们用莫队维护出当前区间 $[l,r]$，在线段树上以时间戳为下标，维护前缀和的最小值。

这个可以化为区间修改，区间查询，不难做到。

可以调调块长，把 $\log$ 丢到根号里，可以做到。

时间复杂度 $O(N\sqrt{N\log N})$。

但由于其巨大的常数，跑起来比 K-D Tree 慢很多。

但四分树由于其丑陋的结构，甚至无法足以通过本题。

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#pragma GCC optimize(2)
#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&
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{
	#define FS 100000
	#define tc() (FA==FB&&(FB=(FA=FI)+fread(FI,1,FS,stdin),FA==FB)?EOF:*FA++)
	#define pc(c) (FC==FE&&(clear(),0),*FC++=c)
	int OT;char oc,FI[FS],FO[FS],OS[FS],*FA=FI,*FB=FI,*FC=FO,*FE=FO+FS;
	I void clear() {fwrite(FO,1,FC-FO,stdout),FC=FO;}
	Tp I void read(Ty& x) {x=0;W(!isdigit(oc=tc()));W(x=(x<<3)+(x<<1)+(oc&15),isdigit(oc=tc()));}
	Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
	Tp I void writeln(Ty x) {W(OS[++OT]=x%10+48,x/=10);W(OT) pc(OS[OT--]);pc('\n');}
}using namespace FastIO;
Cn int N=1.2e5+10,M=N;
int n,Qt,a[N],rt,bl[N],cnt;LL s[N],Ans[N];
struct Que{int l,r,id;}q[N];
class SegmentTree{
	private:
		LL T[N<<2],tg[N<<2];
		#define mid (l+r>>1)
		#define PT CI x=1,CI l=1,CI r=Qt
		#define LT x<<1,l,mid
		#define RT x<<1|1,mid+1,r
		#define PU(x) (T[x]=min(T[x<<1],T[x<<1|1]))
		#define AP(x,v) (T[x]+=v,tg[x]+=v)
		I void PD(CI x){tg[x]&&(AP(x<<1,tg[x]),AP(x<<1|1,tg[x]),tg[x]=0);}
	public:
		I void U(CI L,CI R,LL v,PT){
			if(L<=l&&r<=R) return AP(x,v),void();
			PD(x),L<=mid&&(U(L,R,v,LT),0),R>mid&&(U(L,R,v,RT),0),PU(x);
		}
		I LL Q(CI L,CI R,PT){
			if(L<=l&&r<=R) return T[x];
			LL X=0;return PD(x),L<=mid&&(X=min(X,Q(L,R,LT))),R>mid&&(X=min(X,Q(L,R,RT))),X;
		}
}T;
#define pa pair<int,int>
#define mp make_pair
#define fi first
#define se second
vector<pa> v[N];
#define pb push_back
I void add(CI x){
	for(auto i:v[x]) /*gdb(i.se,i.fi),*/T.U(i.se,n,i.fi);
}
I void del(CI x){
	for(auto i:v[x]) /*gdb(i.se,-i.fi),*/T.U(i.se,n,-i.fi);
}
int main(){
	RI i,o,l,r,S;for(read(n,Qt),S=sqrt(n*6),gdb(S),i=1;i<=n;i++) read(a[i]),s[i]=s[i-1]+a[i];for(i=1;i<=Qt;i++)
		read(o,l,r),o&1?v[l].pb(mp(r-a[l],i)),a[l]=r:(q[++cnt]={l,r,i},0);
	for(i=1;i<=n;i++) bl[i]=(i-1)/S+1;memset(Ans,-1,sizeof(Ans));
	for(sort(q+1,q+cnt+1,[&](Cn Que& x,Cn Que& y){return bl[x.l]^bl[y.l]?x.l<y.l:bl[x.l]&1?x.r<y.r:x.r>y.r;}),l=1,r=0,i=1;i<=cnt;i++){
		W(l>q[i].l) add(--l);W(r<q[i].r) add(++r);W(l<q[i].l) del(l++);W(r>q[i].r) del(r--);
		// cerr<<"Q "<<q[i].id<<" "<<T.Q(1,q[i].id)<<endl;
		Ans[q[i].id]=min(T.Q(1,q[i].id),0LL)+s[q[i].r]-s[q[i].l-1];
	}for(i=1;i<=Qt;i++) ~Ans[i]&&(writeln(Ans[i]),0);
	return clear(),cerr<<clock()<<"ms\n",0;
}

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#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&
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{
	#define FS 100000
	#define tc() (FA==FB&&(FB=(FA=FI)+fread(FI,1,FS,stdin),FA==FB)?EOF:*FA++)
	#define pc(c) (FC==FE&&(clear(),0),*FC++=c)
	int OT;char oc,FI[FS],FO[FS],OS[FS],*FA=FI,*FB=FI,*FC=FO,*FE=FO+FS;
	I void clear() {fwrite(FO,1,FC-FO,stdout),FC=FO;}
	Tp I void read(Ty& x) {x=0;W(!isdigit(oc=tc()));W(x=(x<<3)+(x<<1)+(oc&15),isdigit(oc=tc()));}
	Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
	Tp I void writeln(Ty x) {W(OS[++OT]=x%10+48,x/=10);W(OT) pc(OS[OT--]);pc('\n');}
}using namespace FastIO;
Cn int N=1.2e5+10,M=N;
int n,Q,a[N],rt;LL s[N];
struct Que{int o,l,r,id;}q[N];
class SegmentTree{
	private:
		int cnt;
		struct node{int son[4];LL S,T,A;}T[M*40];
		#define midX (a+c>>1)
		#define midY (b+d>>1)
		#define S0 T[x].son[0],a,b,midX,midY
		#define S1 T[x].son[1],midX+1,b,c,midY
		#define S2 T[x].son[2],a,midY+1,midX,d
		#define S3 T[x].son[3],midX+1,midY+1,c,d
		#define PU(x) (T[x].S=T[T[x].son[0]].S+T[T[x].son[1]].S+T[T[x].son[2]].S+T[T[x].son[3]].S)
		I void PD(CI x){
			T[x].T&&(
			T[x].son[0]&&(T[x].T>0&&T[T[x].son[0]].T<0&&(PD(T[x].son[0]),0),T[T[x].son[0]].S+=T[x].T,T[T[x].son[0]].T+=T[x].T,T[T[x].son[0]].A=min(T[T[x].son[0]].A,T[T[x].son[0]].S),0),
			T[x].son[1]&&(T[x].T>0&&T[T[x].son[1]].T<0&&(PD(T[x].son[1]),0),T[T[x].son[1]].S+=T[x].T,T[T[x].son[1]].T+=T[x].T,T[T[x].son[1]].A=min(T[T[x].son[1]].A,T[T[x].son[1]].S),0),
			T[x].son[2]&&(T[x].T>0&&T[T[x].son[2]].T<0&&(PD(T[x].son[2]),0),T[T[x].son[2]].S+=T[x].T,T[T[x].son[2]].T+=T[x].T,T[T[x].son[2]].A=min(T[T[x].son[2]].A,T[T[x].son[2]].S),0),
			T[x].son[3]&&(T[x].T>0&&T[T[x].son[3]].T<0&&(PD(T[x].son[3]),0),T[T[x].son[3]].S+=T[x].T,T[T[x].son[3]].T+=T[x].T,T[T[x].son[3]].A=min(T[T[x].son[3]].A,T[T[x].son[3]].S),0),
			T[x].T=0);
		}
	public:
		I void B(int &x,CI a,CI b,CI c,CI d,CI Qa,CI Qb,CI Qc,CI Qd){
			!x&&(x=++cnt);if(Qa<=a&&Qb<=b&&c<=Qc&&d<=Qd) return ;
			Qa<=midX&&Qb<=midY&&(B(S0,Qa,Qb,min(Qc,midX),min(Qd,midY)),0),
			Qc>midX&&Qb<=midY&&(B(S1,max(Qa,midX+1),Qb,Qc,min(Qd,midY)),0),
			Qa<=midX&&Qd>midY&&(B(S2,Qa,max(Qb,midY+1),min(Qc,midX),Qd),0),
			Qc>midX&&Qd>midY&&(B(S3,max(Qa,midX+1),max(Qb,midY+1),Qc,Qd),0);
		}
		I void U(int& x,CI a,CI b,CI c,CI d,CI Qa,CI Qb,CI Qc,CI Qd,LL v){
			if(!x) return ;if(Qa<=a&&Qb<=b&&c<=Qc&&d<=Qd) return T[x].T<0&&v>0&&(PD(x),0),T[x].S+=v,T[x].T+=v,T[x].A=min(T[x].A,T[x].S),void();
			PD(x),Qa<=midX&&Qb<=midY&&(U(S0,Qa,Qb,min(Qc,midX),min(Qd,midY),v),0),
			Qc>midX&&Qb<=midY&&(U(S1,max(Qa,midX+1),Qb,Qc,min(Qd,midY),v),0),
			Qa<=midX&&Qd>midY&&(U(S2,Qa,max(Qb,midY+1),min(Qc,midX),Qd,v),0),
			Qc>midX&&Qd>midY&&(U(S3,max(Qa,midX+1),max(Qb,midY+1),Qc,Qd,v),0),PU(x);
		}
		I LL Q(int &x,CI a,CI b,CI c,CI d,CI Qa,CI Qb,CI Qc,CI Qd){
			if(Qa<=a&&Qb<=b&&c<=Qc&&d<=Qd) return T[x].A;
			LL S=0;return PD(x),Qa<=midX&&Qb<=midY&&(S+=Q(S0,Qa,Qb,min(Qc,midX),min(Qd,midY))),
			Qc>midX&&Qb<=midY&&(S+=Q(S1,max(Qa,midX+1),Qb,Qc,min(Qd,midY))),
			Qa<=midX&&Qd>midY&&(S+=Q(S2,Qa,max(Qb,midY+1),min(Qc,midX),Qd)),
			Qc>midX&&Qd>midY&&(S+=Q(S3,max(Qa,midX+1),max(Qb,midY+1),Qc,Qd)),S;
		}
}S;
int main(){
	RI i,o,l,r;for(read(n,Q),i=1;i<=n;i++) read(a[i]),s[i]=s[i-1]+a[i];for(i=1;i<=Q;i++) read(q[i].o,q[i].l,q[i].r);
	for(i=1;i<=Q;i++) !(q[i].o&1)&&(S.B(rt,1,1,n,n,q[i].l,q[i].r,q[i].l,q[i].r),0);
	for(i=1;i<=Q;i++) q[i].o&1?(S.U(rt,1,1,n,n,1,q[i].l,q[i].l,n,q[i].r-a[q[i].l]),a[q[i].l]=q[i].r,0):(writeln(s[q[i].r]-s[q[i].l-1]+S.Q(rt,1,1,n,n,q[i].l,q[i].r,q[i].l,q[i].r)),0);
	return clear(),0;
},0);
	return clear(),cerr<<clock()<<"ms\n",0;
}