CSP202109-5 箱根山岳险天下

@Pelom  July 4, 2022
题解 

题意

对一个数组进行以下几个操作，强制在线

  • 删除数组中最后一个元素
  • 在数组末尾加入一个元素，删掉后又加入的元素与之前元素视为不同的元素
  • 在第$s$次操作后的数组中，将$[l,r]$位置的所有元素乘以$y$，这个操作是永久性的
  • 查询在第$s$次操作后的数组中$[l,r]$位置所有元素目前值的和

数据范围：$1\le m\le 10^5,2\le p\le 2^{30}, mode\in 0,1$

题解

  1. $10\%$数据（小数据）
    树上暴力操作

    • 增加元素：复杂度$O(1)$
    • 删除元素：复杂度$O(1)$
    • 修改元素：确定路径并修改，复杂度$O(m)$
    • 查询元素：确定路径并查询，复杂度$O(m)$

    整体复杂度$O(m^2)$

  2. $10\%$数据（无删除）
    线段树维护

    • 增加元素：线段树单点修改，复杂度$O(\log{m})$
    • 修改元素：线段树区间修改，复杂度$O(\log{m})$
    • 查询元素：线段树区间查询，复杂度$O(\log{m})$

    整体复杂度$O(m\log{m})$

  3. $40\%$数据（可离线）
    树链剖分
    整体复杂度$O(m\log{m})$

  4. $100%$数据
    LCT(Link Cut Tree)
    动态树问题，LCT的模板题
    整体复杂度$O(m\log{m})$
    代码

    #include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
using namespace std;
#define LL long long
#define ls ch[x][0]
#define rs ch[x][1]
#define getch(x)(ch[fa[x]][1]==x)
#define isRoot(x)(ch[fa[x]][0]!=x && ch[fa[x]][1]!=x)
const int N=300000+10;
int m,T;
LL mod;
int ch[N][2],fa[N],st[N],lazyRev[N];
LL val[N],sum[N],lazyMul[N];
void pushdownRev(int x){
    swap(ls,rs);
    lazyRev[x]^=1;
}
void pushdownMul(int x,LL v){
    val[x]=(val[x]*v)%mod;
    sum[x]=(sum[x]*v)%mod;
    lazyMul[x]=(lazyMul[x]*v)%mod;
}
void pushdown(int x){
    if(lazyRev[x]){
        if(ls)
            pushdownRev(ls);
        if(rs)
            pushdownRev(rs);
        lazyRev[x]^=1;
    }
    if(lazyMul[x]!=1){
        if(ls)
            pushdownMul(ls,lazyMul[x]);
        if(rs)
            pushdownMul(rs,lazyMul[x]);
        lazyMul[x]=1;
    }
}
void pushup(int x){
    sum[x]=(sum[ls]+sum[rs]+val[x])%mod;
}
void rotate(int x){
    int y=fa[x],z=fa[y],chk=getch(x),w=ch[x][chk^1];
    if(!isRoot(y))
        ch[z][getch(y)]=x;
    ch[x][chk^1]=y;
    ch[y][chk]=w;
    if(w)
        fa[w]=y;
    fa[y]=x,fa[x]=z;
    pushup(y);
}
void splay(int x){
    int top=0,y=x;
    st[++top]=y;
    for(;!isRoot(y);){
        y=fa[y];
        st[++top]=y;
    }
    for(;top;)
        pushdown(st[top--]);
    for(;!isRoot(x);){
        y=fa[x];
        if(!isRoot(y))
            rotate(getch(x)==getch(y)? y : x);
        rotate(x);
    }
    pushup(x);
}
void access(int x){
    for(int y=0;x;x=fa[y=x]){
        splay(x);
        rs=y;
        pushup(x);
    }
}
void makeRoot(int x){
    access(x);
    splay(x);
    pushdownRev(x);
}
void split(int x,int y){
    makeRoot(x);
    access(y);
    splay(y);
}
void link(int x,int y){
    makeRoot(x);
    fa[x]=y;
}
struct Player{
    int d,f;
    Player(int d=0,int f=0):d(d),f(f){}
}player[N];
vector<int> ranklist[N];
int cur,rnk,tot;
void insertPlayer(int d,LL v){
    ++tot;
    player[tot]=Player(d,cur);
    ++rnk;
    ranklist[rnk].push_back(tot);
    val[tot]=sum[tot]=v;
    lazyMul[tot]=1;
    lazyRev[tot]=0;
    if(cur)
        link(tot,cur);
    cur=tot;
}
int findPlayer(int d,int rnk){
    int l=0,r=ranklist[rnk].size()- 1,ans=0;
    for(;l<=r;){
        int mid=(l+r)>> 1;
        if(player[ranklist[rnk][mid]].d<=d){
            ans=mid;
            l=mid+1;
        }
        else r=mid-1;
    }
    return ranklist[rnk][ans];
}
int main(){
    scanf("%d%lld%d",&m,&mod,&T);
    int op,s,l,r,x,y,A=0;
    for(int d=1;d<=m;++d){
        scanf("%d",&op);
        if(op==1){
            scanf("%d",&x);
            if(T==1)
                x^=A;
            if(x==0){
                cur=player[cur].f;
                --rnk;
            }
            else insertPlayer(d,x);
        }
        else if(op==2){
            scanf("%d%d%d%d",&s,&l,&r,&y);
            if(T==1)
                y^=A;
            l=findPlayer(s,l);
            r=findPlayer(s,r);
            split(l,r);
            pushdownMul(r,y);
        }
        else{
            scanf("%d%d%d",&s,&l,&r);
            l=findPlayer(s,l);
            r=findPlayer(s,r);
            split(l,r);
            A=sum[r];
            printf("%d\n",A);
        }
    }
    return 0;
}

添加新评论