题解 P4743 【[Wind Festival]Energy Center】
niiick
·
·
题解
抢到第一篇题解啦
很裸的splay，然而还是没明白为什么出题人把这题排最简单，可能是蒟蒻我想太复杂了
一开始建立splay要加两个哨兵(烧饼)结点1和n+2，
原始的每个设备序列编号加1，令n+=2
新节点编号为++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
}
```