题解：CF1990F Polygonal Segments

LastKismet · 2026-11-09 12:08:40 · 题解

能组成非退化多边形的条件是二倍最大值小于总和，对于同一个位置作为最大值区间越长是越不劣的。那么一个显然的做法是建出笛卡尔树，若当前点符合条件就返回，否则递归入儿子。一个性质是每次区间和都会减半，深度是 O(\log V) 的。

考虑上线段树。我们对区间维护笛卡尔树，特别地对上文符合条件的点可以只保留他自己、删除其子树内其他元素，因为其他元素及其区间在各方面均不优于该合法点。合并信息类似 FHQ-Treap，可持久化一下，由深度性质知单次复杂度 O(\log V)，那么查询答案只需求所有叶子区间长度最大值即可，容易维护。复杂度 O(n\log V+q\log n\log V)。

const int N=2e5+5;

int n,q;
ll a[N];

int tot;struct node{ll dat,sum,SUM;int len,LEN,ls,rs,ans;}ns[N*40];
il int nnode(ll v){++tot;ns[tot].dat=ns[tot].sum=ns[tot].SUM=v,ns[tot].ans=-1,ns[tot].len=ns[tot].LEN=1,ns[tot].ls=ns[tot].rs=0;return tot;}
il int cnode(int x){ns[++tot]=ns[x];return tot;}
il int upd(int x){
    ns[x].SUM=ns[ns[x].ls].SUM+ns[x].sum+ns[ns[x].rs].SUM;
    ns[x].LEN=ns[ns[x].ls].LEN+ns[x].len+ns[ns[x].rs].LEN;
    ns[x].ans=ns[x].ls||ns[x].rs?max(ns[ns[x].ls].ans,ns[ns[x].rs].ans):ns[x].len;
    return x;
}
il int merge(int x,int y){
    if(!x||!y)return x|y;
    if(ns[x].dat>ns[y].dat){
        x=cnode(x);
        if(ns[x].dat*2<ns[x].SUM+ns[y].SUM)return ns[x].sum=ns[x].SUM+ns[y].SUM,ns[x].len=ns[x].LEN+ns[y].LEN,ns[x].ls=ns[x].rs=0,upd(x);
        return ns[x].rs=merge(ns[x].rs,y),upd(x);
    }else{
        y=cnode(y);
        if(ns[y].dat*2<ns[x].SUM+ns[y].SUM)return ns[y].sum=ns[x].SUM+ns[y].SUM,ns[y].len=ns[x].LEN+ns[y].LEN,ns[y].ls=ns[y].rs=0,upd(y);
        return ns[y].ls=merge(x,ns[y].ls),upd(y);
    }
}
int dat[N<<2];
void build(int x=1,int l=1,int r=n){
    if(l==r)return dat[x]=nnode(a[l]),void();
    int m=l+r>>1;build(x<<1,l,m),build(x<<1|1,m+1,r);
    dat[x]=merge(dat[x<<1],dat[x<<1|1]);
}
void modify(int k,ll v,int x=1,int l=1,int r=n){
    if(l==r)return dat[x]=nnode(v),void();
    int m=l+r>>1;k<=m?modify(k,v,x<<1,l,m):modify(k,v,x<<1|1,m+1,r);
    dat[x]=merge(dat[x<<1],dat[x<<1|1]);
}
int query(int lq,int rq,int x=1,int l=1,int r=n){
    if(lq<=l&&r<=rq)return dat[x];
    int m=l+r>>1;
    if(rq<=m)return query(lq,rq,x<<1,l,m);
    if(m<lq)return query(lq,rq,x<<1|1,m+1,r);
    return merge(query(lq,rq,x<<1,l,m),query(lq,rq,x<<1|1,m+1,r));
}

void INIT(){ns[0].ans=-1;}
void MAIN(){
    tot=0;
    read(n,q);
    rep(i,1,n)read(a[i]);
    build();
    rep(i,1,q){
        ll op,x,y;read(op,x,y);
        if(op==1)put(ns[query(x,y)].ans);
        else modify(x,y);
    }
}