Problem Link

题目大意

给定直方图，保证中间一列最高，求有多少 $[l,r]$，使得仅保留这些行时直方图对称，$q$ 次单点修改，动态维护答案。

数据范围：$n\le 2\times 10^5$。

思路分析

对于对称的两个点，设他们高度为 $x,y(x<y)$，则合法区间要么 $r\le x$，要么 $l>y$，可以把限制看成 $[l,r]$ 与 $[x+1,y]$ 无交。

所以直接线段树，维护所有没被覆盖的极长连续段长度的平方和，只要维护节点左右两侧的最长段大小。

加入和删除区间用标记永久化实现。

时间复杂度 $\mathcal O((n+q)\log n)$。

代码呈现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=2e5+5;
int n,m,q,a[MAXN];
struct info {
	int l,r; ll s; bool c;
	inline friend info operator +(const info &u,const info &v) {
		return {u.l+(u.c?v.l:0),v.r+(v.c?u.r:0),u.s+v.s+1ll*u.r*v.l,u.c&&v.c};
	}
};
const info O={0,0,0,0};
struct SegmentTree {
	static const int MAXS=1<<21|5;
	info tr[MAXS]; int tg[MAXS];
	void psu(int p) { tr[p]=(tg[p<<1]?O:tr[p<<1])+(tg[p<<1|1]?O:tr[p<<1|1]); }
	void init(int l=1,int r=m,int p=1) {
		if(l==r) return tr[p]={1,1,1,1},void();
		int mid=(l+r)>>1;
		init(l,mid,p<<1),init(mid+1,r,p<<1|1);
		psu(p);
	}
	void upd(int ul,int ur,int k,int l=1,int r=m,int p=1) {
		if(ul<=l&&r<=ur) return tg[p]+=k,void();
		int mid=(l+r)>>1;
		if(ul<=mid) upd(ul,ur,k,l,mid,p<<1);
		if(mid<ur) upd(ul,ur,k,mid+1,r,p<<1|1);
		psu(p);
	}
	ll val() { return tg[1]?0:tr[1].s; }
}	T;
void upd(int i,int c) {
	int x=a[i],y=a[n-i+1];
	if(x>y) swap(x,y);
	if(x<y) T.upd(x+1,y,c);
}
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];
	m=a[(n+1)/2],T.init();
	for(int i=1;i<(n+1)/2;++i) upd(i,1);
	cout<<T.val()<<"\n";
	for(int x,v;q--;) cin>>x>>v,upd(x,-1),a[x]=v,upd(x,1),cout<<T.val()<<"\n";
	return 0;
}