自动搬运

查看原文

来自洛谷，原作者为

	niiick **

搬运于2025-08-24 22:03:10，当前版本为作者最后更新于2018-07-11 13:10:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

抢到第一篇题解啦

很裸的splay，然而还是没明白为什么出题人把这题排最简单，可能是蒟蒻我想太复杂了

一开始建立splay要加两个哨兵(烧饼)结点1和n+2， 原始的每个设备序列编号加1，令n+=2

$I \ x$操作，在splay tree中找到第x+1个结点x旋转到根，找到第x+2个结点y旋转到根的右子树， 新节点编号为++n，将其作为y的左子树，更新y和x维护的值

$D \ x$操作，在splay tree中找到第x个结点x旋转到根，找到第x+2个结点y旋转到根的右子树 断掉y的左子树

$QA$操作，用一个变量rem记录删掉了多少节点就好，输出n-2-rem

$QS\ ll\ rr$操作，在splay tree中找到第ll个结点x旋转到根，找到第rr+2个结点y旋转到根的右子树，输出y的左子树维护的值

#include<iostream>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#include<cstdio>
#include<stack>
using namespace std;
typedef double dd;

int read()
{
    int f=1,x=0;
    char ss=getchar();
    while(ss<'0'||ss>'9'){if(ss=='-')f=-1;ss=getchar();}
    while(ss>='0'&&ss<='9'){x=x*10+ss-'0';ss=getchar();}
    return f*x;
}

const int maxn=30010;
int n,m;
int a[maxn][210];
int rt,ch[maxn][2],fa[maxn],rem;
int val[maxn][210],size[maxn];

void update(int p)
{
    int lc=ch[p][0],rc=ch[p][1];
    size[p]=size[lc]+size[rc]+1;
    for(int i=1;i<=m;++i)
    val[p][i]=val[lc][i]+val[rc][i]+a[p][i];
}

void build(int p,int ll,int rr)
{
    if(ll>rr) return;
    int mid=ll+rr>>1;
    fa[mid]=p; size[mid]=1;
    ch[p][mid>p]=mid;
    if(ll==rr)
    {
        for(int i=1;i<=m;++i)val[ll][i]=a[ll][i];
        return;
    }
    build(mid,ll,mid-1); build(mid,mid+1,rr);
    update(mid);
}

void rotate(int &p,int x)
{
    int y=fa[x],z=fa[y];
    int d=(ch[y][0]==x);
    if(y==p) p=x;
    else if(ch[z][0]==y) ch[z][0]=x;
    else ch[z][1]=x;
    fa[y]=x; fa[ch[x][d]]=y; fa[x]=z;
    ch[y][d^1]=ch[x][d]; ch[x][d]=y;
    update(y); update(x);
}

void splay(int &p,int x)
{
    while(x!=p)
    {
        int y=fa[x],z=fa[y];
        if(y!=p)
        {
            if((ch[z][0]==y)^(ch[y][0]==x))rotate(p,x);
            else rotate(p,y);
        }
        rotate(p,x);
    }
}

int find(int p,int k)
{
    int ss=size[ch[p][0]];
    if(k==ss+1) return p;
    else if(k<=ss) return find(ch[p][0],k);
    else return find(ch[p][1],k-ss-1);
}

void ins(int k)
{
    int x=find(rt,k+1); splay(rt,x);
    int y=find(rt,k+2); splay(ch[x][1],y);
    
    ch[y][0]=n; fa[n]=y; size[n]=1;
    for(int i=1;i<=m;++i) val[n][i]=a[n][i];
    update(y); update(x);
}

void del(int k)
{
    int x=find(rt,k); splay(rt,x);
    int y=find(rt,k+2); splay(ch[x][1],y);
    
    fa[ch[y][0]]=0; ch[y][0]=0;
    update(y); update(x); rem++;
}

void get(int ll,int rr)
{
    int x=find(rt,ll); splay(rt,x);
    int y=find(rt,rr+2); splay(ch[x][1],y);
    
    for(int i=1;i<=m;++i)
    printf("%d ",val[ch[y][0]][i]);
    printf("\n");
}

int main()
{
    n=read();m=read();
    for(int i=2;i<=n+1;++i)
    {
        int k=read();
        while(k--)
        {
            int x=read()+1,y=read();
            a[i][x]=y;
        }
    }
    rt=n+3>>1; 
    build(rt,1,n+2); n+=2;
    
    int q=read();
    while(q--)
    {
        char ss[5]; scanf("%s",&ss);
        if(ss[0]=='I')
        {
            int p=read(),k=read(); ++n;
            while(k--)
            {
                int x=read()+1,y=read();
                a[n][x]=y;
            }
            ins(p);
        }
        else if(ss[0]=='D') del(read());
        else if(ss[0]=='Q'&&ss[1]=='A') printf("%d\n",n-2-rem);
        else if(ss[0]=='Q'&&ss[1]=='S') 
        {
            int ll=read(),rr=read();
            get(ll,rr);
        }
    }
    printf("end");
    return 0;
    //niiick
}