题解 P1198 【[JSOI2008]最大数】

· · 题解

翻了好几页题解，没有几个写splay的，那我就发一篇splay的题解吧：

A: 把树的最后一位旋到根，把新点接到根的右孩子处；

Q： 输出维护的ma【】数组，也就是splay维护的区间最大值 有一个地方要注意，假设当前数组长度len=2，进行操作Q 2 此时无法将第0位旋转到根，所以此时特判，出现这个情况的时候直接输出ma【root】就可以了

当然速度不如线段树 = = 

#include"bits/stdc++.h"
using namespace std;

const int maxn = 200010;
int num[maxn];

int temp,len;
int size[maxn];
int val[maxn],ma[maxn],tr[800000];
int ch[maxn][2];
int f[maxn];
int root,tot,t;

void pushup(int x)
{
    int l=ch[x][0],r=ch[x][1];
    size[x]=size[l]+size[r]+1;
    ma[x]=max(val[x],max(ma[l],ma[r])); 
}
int isr(int x)
{
    return ch[f[x]][1]==x;

}
void rotate(int x,int d)
{
    int y=f[x],z=f[y];

    ch[y][!d]=ch[x][d];
    f[ch[x][d]]=y;
    pushup(y);

    int t=isr(y);
    ch[x][d]=y;
    f[y]=x;
    pushup(x);

    if (z) ch[z][t]=x;
    f[x]=z;
    if (z) pushup(z);

}
void splay(int x,int goal)
{
    while (f[x]!=goal)
    {
        int y=f[x],z=f[y];
        if (z==goal) 
         {
            rotate(x,!isr(x));
            break;
         }
        if (ch[z][0]==y)
         {
            if (ch[y][0]==x) rotate(y,1),rotate(x,1);
            else rotate(x,0),rotate(x,1);
         }
        else 
         {
            if (ch[y][1]==x) rotate(y,0),rotate(x,0);
            else rotate(x,1),rotate(x,0); 
         }

    }

    if (!goal) root = x;
 } 
int find(int k,int rt)
{  
    if (k==size[ch[rt][0]]+1) return rt;
    else if (k<=size[ch[rt][0]]) return find(k,ch[rt][0]);
    else return find(k-size[ch[rt][0]]-1,ch[rt][1]);
}
void insert(int k)
{
    if (!root) 
     {  ++len;
        root=++tot;
        val[tot]=k;
        ma[tot]=k;
        size[tot]=1;
        return ;
     }
    int aa=find(len,root);
    ++len;

    splay(aa,0);
    ++tot;
    val[tot]=k;
    size[tot]=1;
    ma[tot]=k;
    ch[aa][1]=tot;
    f[tot]=aa;
    pushup(aa);

}

void print(int rt)
{
    int l=ch[rt][0],r=ch[rt][1];
    printf("%d %d %d %d %d %d\n",rt,val[rt],l,r,ma[rt],size[rt]);
    if (l) print(l);
    if (r) print(r);
}
int main()
{
    int T,D;
   cin>>T>>D;
   while (T--)
    {
        char ss;int pos;
        cin>>ss>>pos;

        if (ss=='A')
         { 
            insert((pos+t)%D);

         }
         else
          {   int tt=len-pos;
              if (!tt) 
               {
                cout<<(t=ma[root])<<endl;
                continue;
               }
            int aa = find(tt,root);
              splay(aa,0);
              t=ma[ch[root][1]];
              cout<<(t)<<endl;

          }

    }

}