FALLEN_GEMINI的平衡树

· · 个人记录

题面改编自《SuperMemo》

题目描述

FALLEN_GEMINI 是个非常可爱的女孩子，喜欢敲敲代码，看看电视……

有一天，她打开电视，开始观看电视节目《SuperMemo》，而她的好朋友 Jackson 正在参加这个节目，于是他花了三七二十八力帮助了她的好朋友 Jackson 。

但我们可爱的女孩子 FALLEN_GEMINI 认为这样的电视节目还不够有趣，于是她邀请了她的小伙伴 屋顶上的小丑 参加她举办的电视节目《FALLEN_GEMINI的平衡树》。

参与者被告知要播放一个记忆游戏。

首先，主持人告诉参与者一系列数字 A_1, A_2, \ldots, A_n。 然后主机对序列执行一系列操作和查询，其中包括：

为了使节目更有趣，参与者有机会转向其他人，这意味着 屋顶上的小丑 在回答查询时感到困难，他可能会打电话给你寻求帮助。

你的任务是观看电视节目并编写一个程序，给出每个查询的正确答案，以便在他打电话时协助 屋顶上的小丑 。

输入格式

第一行一个整数 n。

第二行 n 个整数 A_1,A_2,\ldots, A_n。

第三行一个整数 m，表示操作的数量。

以下 m 行每行一个字符串和若干个整数表示一个操作。

输出格式

对于每个 \text{Find} 操作，输出正确的答案。

样例输入

10
1 2 3 4 5 6 7 8 9 10
9
Add 1 10 1
Reverse 2 8 
Find 1 10 1
Find 2 5 3
Revolve 4 3 7
Insert 5 3
Delete 6
Find 5 6 6
Find 1 10 7

样例输出

2
8
11
7

样例解释

初始数列：1~2~3~4~5~6~7~8~9~10

操作1 将区间 [1,10] 增加1后：\color{red}{\text{2 3 4 5 6 7 8 9 10 11}}

操作2 将区间 [2,8] 翻转后：2~\color{red}{\text{10 9 8 7 6 5 4 3}} 11

操作3 查询区间 [1,10] 中第 1 小的数：2

操作4 查询区间 [2,6] 中第 3 小的数：8

操作5 将区间 [4,6] 逆时针旋转 7 次后：2~10~9 \color{red}{\text{6 8 7}} 5~4~3~11

操作6 在第 3 个数后添加一个值为 5 的点后：2~10~9 \color{red}{\text{5}} 6 ~8~7~5~4~3~11

操作7 删除第 6 个点后：2~10~9~5~6 \color{red}{\text{!}} 7~5~4~3~11

操作8 查询区间 [5,10] 中第 6 小的数：11

操作9 查询区间 [1,10] 中第 7 小的数： 7

子任务

其他

code

因为题目太水了直接上代码吧

#include<bits/stdc++.h> 
#define lson ch[x][0]
#define rson ch[x][1]
using namespace std;
const int MAXN=2e5+10;
const int inf=1e9+7;
int f[MAXN],ch[MAXN][2],lazy[MAXN],flag[MAXN],Min[MAXN],val[MAXN],size[MAXN];
vector<int> a; 
vector<int>::iterator it;
//lazy 自己已经修改，子节点还没有修改 swap自己还没有交换 
int n,m,tot,root;
char c[10];
int read(){int sss=0,fff=1;char ccc;ccc=getchar();while(ccc<'0'||ccc>'9'){if(ccc=='-')fff=-1;ccc=getchar();}while(ccc>='0'&&ccc<='9')sss=(sss<<1)+(sss<<3)+(ccc^'0'),ccc=getchar();return sss*fff;}
inline void updata(int x)//维护结点x的数据 
{
    if(!x) return;
    size[x]=size[lson]+size[rson]+1;
    Min[x]=min(val[x],min(Min[lson],Min[rson])+lazy[x]);
}
inline void updata_add(int x,int op)//维护lazy等区间性数据 
{
    if(!x) return;
    val[x]+=op;lazy[x]+=op;Min[x]+=op;
}
inline void pushdown_swap(int x)//维护下传过程 
{
    swap(lson,rson);
    flag[lson]^=1;flag[rson]^=1; 
    flag[x]=0;
}
inline void pushdown(int x)//下传结点x的lazy和旋转数据 
{
    if(!x) return;
    if(lazy[x]) updata_add(lson,lazy[x]),updata_add(rson,lazy[x]),lazy[x]=0;
    if(flag[x]) pushdown_swap(x);
}//下传数据 
inline int get(int x)//先更新是否交换，再返回x是父亲的左/右孩子 
{
    pushdown(f[x]);
    return ch[f[x]][1]==x;
}
inline void rotate(int x)//旋转结点x 
{
    int old=f[x],oldf=f[old],which=get(x);
    pushdown(x);
    ch[old][which]=ch[x][which^1];f[ch[old][which]]=old;
    ch[x][which^1]=old;f[old]=x;
    f[x]=oldf;
    if(oldf) ch[oldf][ch[oldf][1]==old]=x;
    updata(old);updata(x);
}
inline void splay(int x,int op)//旋转x至成为op的孩子 
{
    for(register int fa;(fa=f[x])!=op;rotate(x))
        if(f[fa]!=op)
            get(fa)==get(x)?rotate(fa):rotate(x);
    if(!op) root=x;
}
inline int findx(int op)//返回排名为op的点的编号 
{
    int x=root;
    while(true)
    {
        pushdown(x);
        if(op<=size[lson])  x=lson;//在左子树上
        else
        {
            op-=size[lson]+1;
            if(!op) return x;//就是这个点
            x=rson; 
        }
    }
}//自带下传数据 找到排名为op的点 
inline void back(int x)//更新数据至根
{
    while(x) updata(x),x=f[x];
}
void newnode(int &rt,int v,int fa)//新建一个结点，值为v，父亲为fa 
{
    rt=++tot;f[rt]=fa;val[rt]=Min[rt]=v;size[rt]=1;
}
inline void insert(int k,int op)//在第k个后面添加一个结点 
{ 
    int l=findx(k),r=findx(k+1);
    splay(l,0);splay(r,l);
    newnode(ch[r][0],op,r);
    updata(r);updata(l);
}
inline void add(int x,int y,int op)//区间[x,y]增加op 
{
    int l=findx(x),r=findx(y+2);
    splay(l,0);splay(r,l);
    updata_add(ch[r][0],op);
    updata(r);updata(l);
}
inline int MIN(int x,int y)//返回区间[x,y]的最小值
{
    int l=findx(x),r=findx(y+2);
    splay(l,0);splay(r,l);
    return Min[ch[r][0]];
}
inline void reverse(int x,int y)//翻转[x,y] 
{
    int l=findx(x),r=findx(y+2);
    splay(l,0);splay(r,l);
    int k=ch[r][0];
    flag[k]^=1;
}
inline void revolve(int x,int y,int T)//旋转[x,y]T次 
{
    int l=findx(x),r=findx(y+2),k=findx(y+1-T),st=findx(x+1);
    splay(l,0);splay(r,l);splay(k,r);
    ch[st][0]=ch[k][1];ch[k][1]=0;f[ch[st][0]]=st;
    back(st);
}
inline void del(int op)//删除排名为op的点 
{
    int l=findx(op),r=findx(op+2);
    splay(l,0);splay(r,l);
    ch[r][0]=0;
    updata(r);updata(l);
}
inline void init()//初始化 
{   
    memset(Min,0x3f3f3f3f,sizeof(Min));
    root=1;tot=2;val[0]=Min[0]=inf;
    val[1]=inf;Min[1]=inf;ch[1][1]=2;size[1]=2;//左哨兵 
    val[2]=inf;Min[2]=inf;f[2]=1;size[2]=1;//右哨兵 
}
inline void GET(int x)
{
    if(!x) return;
    pushdown(x);
    a.push_back(val[x]);
    GET(lson);GET(rson);
}
inline int Find(int x,int y,int k)
{
    int l=findx(x),r=findx(y+2);
    splay(l,0);splay(r,l);
    a.clear();GET(ch[r][0]);//读入整个区间 
    it=a.begin()+k-1;
    nth_element(a.begin(),it,a.end());
    return *it;
}
int main()
{
//  freopen("bt.in","r",stdin);
//  freopen("bt.out","w",stdout);
    init();n=read();
    for(register int i=1;i<=n;++i) insert(i,read());
    m=read();
    for(int i=1;i<=m;i++)
    {
        int pos,len,x,op,T,k;
        scanf("%s",c);
        if(c[0]=='A') pos=read(),len=read(),op=read(),add(pos,pos+len-1,op);
        else if(c[0]=='I') x=read(),pos=read(),insert(pos+1,x);
        else if(c[0]=='F')
        {
            pos=read();len=read();k=read();
            if(k==1) printf("%d\n",MIN(pos,pos+len-1));
            else printf("%d\n",Find(pos,pos+len-1,k));
        }
        else if(c[0]=='D') pos=read(),del(pos);
        else if(c[3]=='o') {pos=read(),len=read(),T=read(),T%=len;if(T) revolve(pos,pos+len-1,T);}
        else if(c[3]=='e') pos=read(),len=read(),reverse(pos,pos+len-1);
    }
    return 0;
}