题解：P10796 『SpOI - R1』我看到了，谢谢你们

是青白呀 · 2024-07-22 08:57:20 · 题解

青山是不会老的。

首先对原串建立失配树，根节点应当为空串。

对于一个人 x，若要确保他能够当总统，那么必须要控制拥有票数半数以上的人。x 能控制的人显然是他的子树内的任意一个子子树，因此我们不妨找到树上 a 的带权重心 c，可行的 x 只有 0 到 c 的链上的所有点。

考虑如何维护带修带权重心。这是一个经典 trick：我们将每个点复制出权值那么多个，并拍到 dfs 序上去。由于该题中要求带权重心对应子树的权值和必须要严格大于总权值的一半，因此其子树在 dfs 序上的对应区间一定经过这个 dfs 序的中点。我们找到 dfs 序上 \lceil \frac{\sum a_i}2\rceil 处的点 p，则带权重心 c 一定是 p 的首个子树对应区间长度大于等于 \lceil \frac{\sum a_i}2\rceil 的祖先，使用倍增即可找到。用线段树二分的方式维护 a 即可。

找到 c 后，问题变为找一个 0\to c 上的点 x，以及一个 x\to c 上的点 y，最小化 w_x+\sum_{v\in\operatorname{subtree}_y}w_v 的值。不妨将答案记录在点 y 上。考虑在线段树上维护每个点子树的 w 和 sum、以及该点作为 y 时的答案 ans。一个点 u 被改小时，会更新 0\to u 上的子树和，同时给 u 子树中的每个点提供了一个 x 的可能更优的选择。因此对于链上的情况，我们树剖直接修改 sum 和 ans；对于 u 子树内的点，我们令 ans=\min(ans,sum+w_u) 即可。这个东西同样可以打 tag 维护。

倍增和树剖的复杂度都是两个 \log，因此最终总复杂度为 O((n+q)\log^2 n)。

#include<bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define repp(i,j,k) for(int i=j;i>=k;i--)
#define ls(x) x*2
#define rs(x) x*2+1
#define mp make_pair
#define sec second
#define fir first
#define pii pair<int,int>
#define int long long
#define lowbit(i) i&-i
#define double long double
#define qingbai 666
using namespace std;
typedef long long ll;
const int N=1e5+20,S=(1<<20)+5,mo1=1e9+9,base1=19491001,mo2=998244353,base2=19260817,inf=(ll)1e18+7;
void read(int &p){
    int x=0,w=1;
    char ch=0;
    while(!isdigit(ch)){
        if(ch=='-')w=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    p=x*w;
}
int T;
int n,q,tp,a[N],w[N];
string s;
int kmp[N];
vector<int>e[N];
int fa[N][20],dep[N],topp[N],dfn[N],cntp,sz[N],hson[N],nw[N];
void dfs1(int x){
    dep[x]=dep[fa[x][0]]+1,sz[x]=1,hson[x]=0;
    rep(i,1,17)
        fa[x][i]=fa[fa[x][i-1]][i-1];
    for(auto j:e[x]){
        dfs1(j);
        if(!hson[x]||sz[hson[x]]<sz[j])hson[x]=j;
        sz[x]+=sz[j]; 
    }
}
void dfs2(int x,int toppos){
    topp[x]=toppos,dfn[x]=++cntp,nw[cntp]=x;
    if(hson[x])dfs2(hson[x],toppos);
    for(auto j:e[x]){
        if(j==hson[x])continue;
        dfs2(j,j);
    }
}
struct seg1{//单点修改，线段树上二分. 
    int t[4*N],maxn[4*N],maxp[4*N];
    void pushup(int x){
        t[x]=t[ls(x)]+t[rs(x)];
        if(maxn[ls(x)]>maxn[rs(x)])maxn[x]=maxn[ls(x)],maxp[x]=maxp[ls(x)];
        else maxn[x]=maxn[rs(x)],maxp[x]=maxp[rs(x)];
    }
    void build(int x,int le,int ri){
        if(le==ri){
            t[x]=a[nw[le]],maxn[x]=t[x],maxp[x]=le;
            return;
        }
        int mid=(le+ri)>>1;
        build(ls(x),le,mid),build(rs(x),mid+1,ri);
        pushup(x);
    }
    void modify(int x,int le,int ri,int p,int v){
        if(le==ri){
            t[x]=maxn[x]=v;
            return;
        }
        int mid=(le+ri)>>1;
        if(p<=mid)modify(ls(x),le,mid,p,v);
        else modify(rs(x),mid+1,ri,p,v);
        pushup(x);
    }
    int query(int x,int le,int ri,int v){
        if(le==ri)return le;
        int mid=(le+ri)>>1;
        if(t[ls(x)]<v)return query(rs(x),mid+1,ri,v-t[ls(x)]);
        else return query(ls(x),le,mid,v);
    }
    int querysum(int x,int le,int ri,int ql,int qr){
        if(ql<=le&&qr>=ri)return t[x];
        int mid=(le+ri)>>1,res=0;
        if(ql<=mid)res+=querysum(ls(x),le,mid,ql,qr);
        if(qr>mid)res+=querysum(rs(x),mid+1,ri,ql,qr);
        return res;
    } 
}T1;
struct seg2{//区间加减，区间取min
    int sum[4*N],ans[4*N],dectag[4*N],mintag[4*N];
    void pushup(int x){
        sum[x]=min(sum[ls(x)],sum[rs(x)]);
        ans[x]=min(ans[ls(x)],ans[rs(x)]);
    }
    void pushdown(int x){
        sum[ls(x)]+=dectag[x],sum[rs(x)]+=dectag[x],ans[ls(x)]+=dectag[x],ans[rs(x)]+=dectag[x];
        dectag[ls(x)]+=dectag[x],dectag[rs(x)]+=dectag[x];
        dectag[x]=0;
        mintag[ls(x)]=min(mintag[ls(x)],mintag[x]),mintag[rs(x)]=min(mintag[rs(x)],mintag[x]);
        ans[ls(x)]=min(ans[ls(x)],sum[ls(x)]+mintag[ls(x)]),ans[rs(x)]=min(ans[rs(x)],sum[rs(x)]+mintag[rs(x)]);
    }
    void build(int x,int le,int ri){
        sum[x]=0,ans[x]=inf,mintag[x]=inf,dectag[x]=0;
        if(le==ri)return;
        int mid=(le+ri)>>1;
        build(ls(x),le,mid),build(rs(x),mid+1,ri); 
    }
    void add(int x,int le,int ri,int ql,int qr,int v){
        if(ql<=le&&qr>=ri){
            sum[x]+=v,ans[x]+=v,dectag[x]+=v;
            return;
        }
        pushdown(x);
        int mid=(le+ri)>>1;
        if(ql<=mid)add(ls(x),le,mid,ql,qr,v);
        if(qr>mid)add(rs(x),mid+1,ri,ql,qr,v);
        pushup(x);
    }
    void modify(int x,int le,int ri,int ql,int qr,int v){
        if(ql<=le&&qr>=ri){
            ans[x]=min(ans[x],sum[x]+v);
            mintag[x]=min(mintag[x],v);
            return;
        }
        pushdown(x);
        int mid=(le+ri)>>1;
        if(ql<=mid)modify(ls(x),le,mid,ql,qr,v);
        if(qr>mid)modify(rs(x),mid+1,ri,ql,qr,v);
        pushup(x);
    }
    int query(int x,int le,int ri,int ql,int qr){
        if(ql<=le&&qr>=ri){
            return ans[x];
        }
        pushdown(x);
        int mid=(le+ri)>>1,res=inf;
        if(ql<=mid)res=min(res,query(ls(x),le,mid,ql,qr));
        if(qr>mid)res=min(res,query(rs(x),mid+1,ri,ql,qr));
        pushup(x);
        return res; 
    }
}T2;
void addroad(int x,int v){
    while(x>=0){
        T2.add(1,1,n+1,dfn[topp[x]],dfn[x],v);
        x=fa[topp[x]][0];
    }
}
int getans(){
    int res=inf;
    int nsum=T1.t[1],targ=T1.query(1,1,n+1,(nsum+1)/2);
    if(T1.maxn[1]>nsum/2)res=w[nw[T1.maxp[1]]];
    targ=nw[targ];
    repp(i,17,0){
        int nxtp=fa[targ][i];
        if(nxtp>=0&&T1.querysum(1,1,n+1,dfn[nxtp],dfn[nxtp]+sz[nxtp]-1)<=nsum/2)targ=nxtp;
    }
    if(T1.querysum(1,1,n+1,dfn[targ],dfn[targ]+sz[targ]-1)<=nsum/2)targ=fa[targ][0];
    while(targ>=0){
        res=min(res,T2.query(1,1,n+1,dfn[topp[targ]],dfn[targ]));
        targ=fa[topp[targ]][0];
    }
    return res;
}
void solve(){
    read(n),read(q),read(tp);
    cin>>s;
    rep(i,0,n)
        e[i].clear();
    for(int i=1,j=0;i<n;i++){
        while(j&&s[i]!=s[j])
            j=kmp[j-1];
        if(s[i]==s[j])j++;
        kmp[i]=j;
    }
    rep(i,0,n)
        read(a[i]),read(w[i]); 
    fa[0][0]=-1,cntp=0;
    rep(i,1,n)
        fa[i][0]=kmp[i-1],e[kmp[i-1]].push_back(i);
    dfs1(0),dfs2(0,0);
    T1.build(1,1,n+1),T2.build(1,1,n+1);
    rep(i,0,n){//初始化 T2. 
        addroad(i,w[i]);
        T2.modify(1,1,n+1,dfn[i],dfn[i]+sz[i]-1,w[i]);
    }

    int lans=getans();
    printf("%lld\n",lans),lans=abs(lans);
    while(q--){
        int op,p,v;
        read(op),read(p),read(v);
        op^=(lans*tp),p^=(lans*tp);
        if(v<=0)v=(-v)^(lans*tp),v*=-1;
        else v^=lans*tp;
        if(op==1)T1.modify(1,1,n+1,dfn[p],v);
        if(op==2)addroad(p,v-w[p]),T2.modify(1,1,n+1,dfn[p],dfn[p]+sz[p]-1,v),w[p]=v;
        lans=getans();
        printf("%lld\n",lans),lans=abs(lans);
    }
}
signed main(){
    read(T);
    while(T--)
        solve();
    return 0;
}