题解：P9790 [ROIR 2020] 海报 (Day 2)

#include<bits/stdc++.h>
#define int long long
#define mp(a,b) make_pair(a,b)
using namespace std;

inline int read(){
	int a=0,b=1;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-')	b=-1;
		c=getchar(); 
	}
	while(isdigit(c)){
		a=(a<<1)+(a<<3)+(c-'0');
		c=getchar();
	}
	return a*b;
}
inline void write(int x){
	if(x<0)	putchar('-'),x=-x;
	if(x>=10)	write(x/10);
	putchar(x%10+48);
}
inline void write1(int x){
	write(x),putchar(' ');
}
inline void write2(int x){
	write(x),putchar('\n'); 
}
struct node{
	int l,r;	//代表这里的区间 
	int ans[4][4];	//ans[x][y]  代表选取这里导致的左边有 x 个点 右边有 y 个点 总和不能大于 3  
}tree[2*114514];
int n,q;
int a[20*2025];	//40050 
void pushup(int id){
	int l=tree[id].l,r=tree[id].r; 
	int l1=tree[id*2].l,r1=tree[id*2].r;
	int l2=tree[id*2+1].l,r2=tree[id*2+1].r;
	for(int i=0;i<=3;i++){
		for(int j=0;j<=3;j++){
			tree[id].ans[i][j]=0;	//这种情况先初始化  
		}
	} 
	//接下来就是 [l1,l2] 和 [r1,r2] 的区间合并 
	//注意一种新的思路：一开始不考虑若干人走在一起的情况 等到询问时统一处理 
//	for(int i=0;i<=min(3,r1-l1+1);i++){
//		for(int j=0;j<=min(3,r2-l2+1);j++){
//			//仅需考虑中间两个 
//		}
//	} 
	for(int i=0;i<=min(3ll,r1-l1+1);i++){
		for(int j=0;j<=min(3ll,r1-l1+1);j++){
			//有一个地方必须剪枝：[i,j] 代表的区间不合法 
			if((i+j>(r1-l1+1))&&(i+j)<2*(r1-l1+1)){
//				if(id==2)	cout<<i<<' '<<j<<' ',cout<<"谭总的世界-031"<<endl;
				continue;	//这种情况区间不合法 直接忽略   
			}	
			if(i==(r1-l1+1)&&j==0){
//				if(id==2)	cout<<"谭总的世界-032"<<endl;
				continue;
			}
			if(j==(r1-l1+1)&&i==0){
//				if(id==2)	cout<<"谭总的世界-033"<<endl; 
				continue;	//剔除所有的不合法情况  
			}
			for(int i1=0;i1<=min(3ll,r2-l2+1);i1++){
				if(j+i1>=4)	continue;	//这种情况忽略考虑  
				for(int j1=0;j1<=min(3ll,r2-l2+1);j1++){
					if((i1+j1)>(r2-l2+1)&&(i1+j1)<2*(r2-l2+1))	continue;	//这也是不合法的区间 忽略  
					//接下来转移到的地方称为 [L,R] 注意改成了大写 
					if(i1==(r2-l2+1)&&j1==0)	continue;
					if(j1==(r2-l2+1)&&i1==0)	continue;	//这些情况都不合法 
					int L=0,R=0;	//初值实际上没有任何意义 只是一种摆设 
					if(i==(r1-l1+1)&&j==(r1-l1+1)){
						//代表这里左边是满的 
						L=i+i1;	//这就是左边的情况  
					} 
					else 	L=i;
					if(L>=4)	continue;	//也没有意义   
					if(i1==(r2-l2+1)&&j1==(r2-l2+1)){
						R=j+j1;
					}
					else	R=j1;	//最右侧的点 
					tree[id].ans[L][R]=max(tree[id].ans[L][R],tree[id*2].ans[i][j]+tree[id*2+1].ans[i1][j1]);
					//这是真正有用的转移的部分！  
				}
			}
		}
	}
} 
void build(int id,int l,int r){
	tree[id].l=l,tree[id].r=r;
	if(l==r){
		tree[id].ans[0][0]=0;
		tree[id].ans[1][1]=a[l];	//代表这里的取值系数  
		return;
	}
	int mid=l+r>>1;
	build(id*2,l,mid),build(id*2+1,mid+1,r);
	pushup(id);
}
void modify(int id,int x,int y){
	int l=tree[id].l,r=tree[id].r;
	if(l==r){
		tree[id].ans[0][0]=0;
		tree[id].ans[1][1]=y;	//直接处理成这样 
		return; 
	}
	int mid=l+r>>1;
	if(x<=mid)	modify(id*2,x,y);
	else	modify(id*2+1,x,y);
	pushup(id);
}
void query(){
	//全部都在 tree[1] 上询问 
	int include13=0;	//代表最终答案  
	for(int i=0;i<=3;i++){
		for(int j=0;j<=3;j++){
			if(i+j>=4)	continue;	//只考虑较小情况下的答案 
			include13=max(include13,tree[1].ans[i][j]); 
//			cout<<'#'<<i<<' '<<j<<' '<<tree[1].ans[i][j]<<endl;
		} 
	} 
	write2(include13);	//代表输出目前的解  
	return;
} 
signed main(){
	n=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
	}
	build(1,1,n);
//	cout<<'#'<<tree[4].ans[2][2]<<endl;
//	cout<<'#'<<tree[5].ans[1][1]<<endl;
//	cout<<'#'<<tree[2].ans[3][3]<<endl;
	query();	//把 query 处理成这种 void 函数 也是很妙的  
	q=read();
	while(q--){
		int x=read(),y=read();
		modify(1,x,y);
		query();
	} 
	putchar('\n');
	return 0;
}//全世界 好像只有我疲惫