自动搬运

查看原文

来自洛谷，原作者为

	TTpandaS 幾重にも辛酸を舐め、七難八苦を越え、艱難辛苦の果、満願成就に至る

搬运于2025-08-24 23:15:16，当前版本为作者最后更新于2025-05-24 14:36:30，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

对于某一层，如果配对的数量为 $\dfrac{n}{2}$，那么该层对称。

每段连续对称的长度为 $l_i$，答案为 $\sum \dfrac{l_i \times (l_i+1)}{2}$。

直接维护配对数量为 $\dfrac{n}{2}$ 的层不好维护，考虑到其为最大值，设 $f_i$ 为区间内最大值组成的连续段长度，直接维护该区间的最大值对应的答案 $\sum \dfrac{f_i \times (f_i+1)}{2}$ 即可。

合并的时候记录一下区间左侧最大值的数量和最小值即可。

（愚蠢的考场代码，在线段树里维护了一些没用的值）

#include<bits/stdc++.h>
#define int long long
#define lc p<<1
#define rc p<<1|1
using namespace std;
const int N=2e5+5,V=654205;
int n,q;
int a[N];
struct tree{
	int l,r;
	int maxn,tot;
	int lt,rt;
	int maxans;
	int ans;
	int tag;
	friend tree operator+(tree x,tree y){
		tree res;
		res.l=x.l;
		res.r=y.r;
		if(x.maxn>y.maxn){
			res.maxn=x.maxn;
			res.tot=x.tot;
			res.lt=x.lt;
			res.rt=0;
			res.maxans=x.maxans;
			if(res.maxn==n/2){
				res.ans=x.ans;
			}
			else{
				res.ans=0;
			}
		}
		else if(x.maxn<y.maxn){
			res.maxn=y.maxn;
			res.tot=y.tot;
			res.lt=0;
			res.rt=y.rt;
			res.maxans=y.maxans;
			if(res.maxn==n/2){
				res.ans=y.ans;
			}
			else{
				res.ans=0;
			}
		}
		else if(x.maxn==y.maxn){
			res.maxn=x.maxn;
			res.tot=x.tot+y.tot;
			if(x.lt==x.r-x.l+1){
				res.lt=x.lt+y.lt;
			}
			else{
				res.lt=x.lt;
			}
			if(y.rt==y.r-y.l+1){
				res.rt=y.rt+x.rt;
			}
			else{
				res.rt=y.rt;
			}
			res.maxans=x.maxans+y.maxans;
			res.maxans-=x.rt*(x.rt+1)/2;
			res.maxans-=y.lt*(y.lt+1)/2;
			res.maxans+=(x.rt+y.lt)*(x.rt+y.lt+1)/2; 
			if(res.maxn==n/2){
				res.ans=res.maxans;
			}
			else{
				res.ans=0;
			}
		}
		res.tag=0;
		return res;
	}
}t[V*4];
void pushup(int p){
	t[p]=t[lc]+t[rc];
}
void pushdown(int p){
	if(t[p].tag){
		t[lc].maxn+=t[p].tag;
		if(t[lc].maxn==n/2){
			t[lc].ans=t[lc].maxans;
		}
		else{
			t[lc].ans=0;
		}
		t[lc].tag+=t[p].tag;
		t[rc].maxn+=t[p].tag;
		if(t[rc].maxn==n/2){
			t[rc].ans=t[rc].maxans;
		}
		else{
			t[rc].ans=0;
		}
		t[rc].tag+=t[p].tag;		
		t[p].tag=0;
	}
}
void build(int p,int l,int r){
	t[p].l=l,t[p].r=r,t[p].tag=0;
	if(l==r){
		t[p].lt=t[p].rt=1;
		t[p].maxn=0;
		t[p].tot=1;
		t[p].maxans=1;
		t[p].ans=0;
		return;
	}
	int mid=(t[p].l+t[p].r)>>1;
	build(lc,l,mid);
	build(rc,mid+1,r);
	pushup(p);
}
void add(int p,int l,int r,int x){
	if(l>r){
		return;
	}
	if(l<=t[p].l&&t[p].r<=r){
		t[p].maxn+=x;
		if(t[p].maxn==n/2){
			t[p].ans=t[p].maxans;
		}
		else{
			t[p].ans=0;
		}
		t[p].tag+=x;
		return;
	}
	pushdown(p);
	int mid=(t[p].l+t[p].r)>>1;
	if(l<=mid){
		add(lc,l,r,x);
	}
	if(mid+1<=r){
		add(rc,l,r,x);
	}
	pushup(p);
	//cout<<t[p].l<<' '<<t[p].r<<' '<<t[p].maxn<<' '<<t[p].tot<<' '<<t[p].lt<<' '<<t[p].rt<<' '<<t[p].maxans<<' '<<t[p].ans<<'\n';
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	build(1,1,a[(n+1)/2]); 
	for(int i=1,j=n;i<=n/2;i++,j--){
		add(1,1,min(a[i],a[j]),1);
		add(1,max(a[i],a[j])+1,a[(n+1)/2],1); 
	}
	cout<<t[1].ans<<'\n';
	while(q--){
		int x,y;
		cin>>x>>y;
		add(1,1,min(a[x],a[n-x+1]),-1);
		add(1,max(a[x],a[n-x+1])+1,a[(n+1)/2],-1);
		a[x]=y;
		add(1,1,min(a[x],a[n-x+1]),1);
		add(1,max(a[x],a[n-x+1])+1,a[(n+1)/2],1);
		cout<<t[1].ans<<'\n';
	}
	return 0;
}