P3273 题解

· · 题解

可以强制在线的线段树做法。

如果你不会线段树合并，左转 P4556【模板】线段树合并。

对于第 i 个点，建一颗线段树，并将第 i 个位置的值改为 a_i。

再用一个并查集维护这个点所在的连通块，第 i 个点初始属于第 i 个连通块。

再用一个线段树（称为总线段树）维护连通块的最大值。

再用一个变量（记为 d）维护所有点的增加量。

对于操作 U，先找到 x 和 y 对应的连通块编号 v_x 和 v_y。 如果不同，在并查集中将 v_x 合并到 v_y，并将第 v_x 个线段树合并到第 v_y 个线段树，然后在总线段树中将 v_x 的值改为极小值，v_y 的值改为该连通块内的最大值。

对于操作 A1，先找到 x 对应的连通块编号 v_x，然后修改第 v_x 个线段树第 x 个位置为 v，修改后在总线段树中修改第 v_x 个连通块的值。

对于操作 A2，先找到 x 对应的连通块编号 v_x，然后在该树的根节点打标记，并在总线段树中做对应修改。

对于操作 A3，将 d 增加 v。

对于所有的 F 类操作，在输出答案时要将线段树中的查询结果增加 d 后输出。

对于 F1 操作，先找到 x 对应的连通块编号 v_x，然后查询第 v_x 个线段树第 x 个位置的值。

对于 F2 操作，先找到 x 对应的连通块编号 v_x，然后查询结果为第 v_x 个线段树根节点上的值。

对于 F3 操作，查询结果为总线段树的根节点的值。

注意：合并线段树时一定要下放懒标记！

code:

#include<bits/stdc++.h>
using namespace std;
const int N=300010;
int f[N];
int find(int x){return x==f[x]?f[x]:f[x]=find(f[x]);}
int rt[N];
int val[N<<5],ls[N<<5],rs[N<<5],lazy[N<<5],idx;
void pushdown(int k){
    if(ls[k]){lazy[ls[k]]+=lazy[k];val[ls[k]]+=lazy[k];}
    if(rs[k]){lazy[rs[k]]+=lazy[k];val[rs[k]]+=lazy[k];}
    lazy[k]=0;
}
void update(int&k,int l,int r,int x,int v){
    if(!k)  k=++idx;
    if(l==r){val[k]+=v;return;}
    pushdown(k);
    int mid=(l+r)>>1;
    if(x<=mid)  update(ls[k],l,mid,x,v);
    else    update(rs[k],mid+1,r,x,v);
    val[k]=max(val[ls[k]],val[rs[k]]);
}
int query(int k,int l,int r,int x){
    if(l==r)    return val[k];
    pushdown(k);
    int mid=(l+r)>>1;
    if(x<=mid)  return query(ls[k],l,mid,x);
    else    return query(rs[k],mid+1,r,x);
}
void merge(int&k1,int&k2){
    if(!k1){k1=k2;return;}
    if(!k2) return;
    pushdown(k1);pushdown(k2);
    merge(ls[k1],ls[k2]);
    merge(rs[k1],rs[k2]);
    val[k1]=max(val[ls[k1]],val[rs[k1]]);
}
int tree[N<<2];
void update2(int k,int l,int r,int x,int v){
    if(l==r){tree[k]=v;return;}
    int mid=(l+r)>>1;
    if(x<=mid)  update2(k<<1,l,mid,x,v);
    else    update2(k<<1|1,mid+1,r,x,v);
    tree[k]=max(tree[k<<1],tree[k<<1|1]);
}
int gl;
int n;
char op[4];
int main(){
    //freopen("test.in","r",stdin);
    //freopen("test1.out","w",stdout);
    val[0]=-0x3f3f3f3f;
    memset(tree,-0x3f,sizeof tree);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)   f[i]=i;
    for(int i=1;i<=n;i++){
        int x;scanf("%d",&x);
        update(rt[i],1,n,i,x);
        update2(1,1,n,i,x);
    }
    int q;scanf("%d",&q);
    while(q--){
        scanf("%s",op);
        if(op[0]=='U'){
            int x,y;scanf("%d%d",&x,&y);
            x=find(x);y=find(y);
            if(x!=y){
                int mx=max(val[rt[x]],val[rt[y]]);
                update2(1,1,n,y,mx);
                update2(1,1,n,x,-0x3f3f3f3f);
                f[x]=y;
                merge(rt[y],rt[x]);
            }
        }
        if(op[0]=='A'){
            if(op[1]=='1'){
                int x,v;scanf("%d%d",&x,&v);
                update(rt[find(x)],1,n,x,v);
                update2(1,1,n,find(x),val[rt[find(x)]]);
            }
            if(op[1]=='2'){
                int x,v;scanf("%d%d",&x,&v);
                val[rt[find(x)]]+=v;
                lazy[rt[find(x)]]+=v;
                update2(1,1,n,find(x),val[rt[find(x)]]);
            }
            if(op[1]=='3'){
                int v;scanf("%d",&v);
                gl+=v;
            }
        }
        if(op[0]=='F'){
            if(op[1]=='1'){
                int x;scanf("%d",&x);
                printf("%d\n",query(rt[find(x)],1,n,x)+gl);
            }
            if(op[1]=='2'){
                int x;scanf("%d",&x);
                printf("%d\n",val[rt[find(x)]]+gl);
            }
            if(op[1]=='3'){
                printf("%d\n",tree[1]+gl);
            }
        }
    }
    return 0;
}