CF1990F Polygonal Segments 题解

题目大意

给定长度为 $n$ 的序列 $a_1\sim a_n$，有 $q$ 次操作：

• 1 l r：查询区间 $[l,r]$ 中最长的子区间 $[x,y]$，使得用 $a_x\sim a_y$ 作为边长能构成一个 $(y-x+1)$ 边形。若不存在输出 $-1$。
• 2 i x：将 $a_i$ 修改为 $x$。

$n,q\le 2\times 10^5$，$a_i\le 10^{12}$。所有测试点 $n$ 总和、$q$ 总和均不超过 $2\times 10^5$。

核心性质

一个区间 $[x,y]$ 能构成多边形，当且仅当 最大边严格小于其余边之和，即：

等价于该区间不存在绝对众数（没有任何一个数超过总和的一半）。

关键观察

1. 扩展单调性：若 $a_{x-1}<\sum_{i=x}^y a_i$，则将左端点扩展到 $x-1$ 后区间仍然合法。这是因为新加入的边小于原有总和，仍满足不等式。
2. 候选后缀：考虑以 $i$ 开头的后缀 $a[i,n]$，若它要参与产生最优解，必须满足 $a_{i-1}\ge \sum_{j\ge i} a_j$。否则根据上述扩展性质，可以直接将左端点向左扩展得到一个不比它差的合法区间。
   满足该条件的后缀只有 $O(\log V)$ 个，因为每增加一个这样的后缀，区间总和至少翻倍（$V=10^{12}$）。
3. 同理，候选前缀也只有 $O(\log V)$ 个。

线段树维护信息

利用线段树维护每个区间内的候选前缀集合 pr、候选后缀集合 sf，以及区间内的最优答案 ans。

合并左右儿子：

• 前缀集合 = 左儿子的前缀集合 + 右儿子中满足“该位置的值 ≥ 左儿子总和 + 此前已累加和”的前缀。
• 后缀集合同理，方向相反。
• 合并答案：枚举左儿子的后缀与右儿子的前缀，用双指针按最大值排序后，检查是否满足 $2\max <$ 两侧总和，更新区间长度。

由于每个区间的 pr / sf 大小均为 $O(\log V)$，单次合并复杂度 $O(\log V)$，总复杂度 $O(n\log V + q\log n \log V)$，可以通过。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=2e5+5;
int n,q;
ll a[MAXN];
struct seg { int x; ll s; };
struct info {
	int l,r,ans;
	ll sum;
	vector<seg> pr,sf;
	info() { l=r=sum=0,ans=-1,pr.clear(),sf.clear(); }
	info(int i) { l=r=i,ans=-1,sum=a[i],pr=sf={{i,0}}; }
	inline friend info operator +(const info &L,const info &R) {
		if(!L.l||!R.r) return L.l?L:R;
		info X;
		X.l=L.l,X.r=R.r,X.sum=L.sum+R.sum;
		X.ans=max(L.ans,R.ans),X.pr=L.pr,X.sf=R.sf;
		for(auto i:R.pr) {
			if(a[i.x]>=L.sum+i.s) X.pr.push_back({i.x,L.sum+i.s});
		}
		for(auto i:L.sf) {
			if(a[i.x]>=i.s+R.sum) X.sf.push_back({i.x,i.s+R.sum});
		}
		vector<seg> vl=L.sf,vr=R.pr;
		int sl=vl.size(),sr=vr.size();
		vl.push_back({L.l-1,L.sum});
		vr.push_back({R.r+1,R.sum});
		auto chk=[&](int i,int j) {
			if(max(a[vl[i].x],a[vr[j].x])*2<vl[i+1].s+vr[j+1].s) {
				X.ans=max(X.ans,vr[j+1].x-vl[i+1].x-1);
			}
		};
		for(int i=0,j=-1;i<sl;++i) {
			for(;j+1<sr&&a[vl[i].x]>=a[vr[j+1].x];++j);
			if(j>=0) chk(i,j);
		}
		for(int i=0,j=-1;i<sr;++i) {
			for(;j+1<sl&&a[vr[i].x]>=a[vl[j+1].x];++j);
			if(j>=0) chk(j,i);
		}
		return X;
	}
};
struct zkwSegt {
	info tr[1<<19];
	int N;
	void init() {
		for(N=1;N<=n;N<<=1);
		for(int i=1;i<(N<<1);++i) tr[i]=info();
		for(int i=1;i<=n;++i) tr[i+N]=info(i);
		for(int i=N-1;i;--i) tr[i]=tr[i<<1]+tr[i<<1|1];
	}
	void upd(int x) {
		for(tr[x+N]=info(x),x=(x+N)>>1;x;x>>=1) tr[x]=tr[x<<1]+tr[x<<1|1];
	}
	int qry(int l,int r) {
		info sl=info(l),sr=info(r);
		for(l+=N,r+=N;l^r^1;l>>=1,r>>=1) {
			if(~l&1) sl=sl+tr[l^1];
			if(r&1) sr=tr[r^1]+sr;
		}
		return (sl+sr).ans;
	}
} T;
void solve() {
	cin>>n>>q;
	for(int i=1;i<=n;++i) cin>>a[i];
	T.init();
	for(ll op,x,y;q--;) {
		cin>>op>>x>>y;
		if(op==1) cout<<T.qry(x,y)<<"\n";
		else a[x]=y,T.upd(x);
	}
}
signed main() {
	ios::sync_with_stdio(false);
	int _; cin>>_;
	while(_--) solve();
	return 0;
}