BZOJ4415:[SHOI2013]发牌(线段树)

Myth丶恋晨 2022-01-10 03:49 216阅读 0赞

## Description ##

假设一开始，荷官拿出了一副新牌，这副牌有N张不同的牌，编号依次为1到N。由于是新牌，所以牌是按照顺序排好的，从牌库顶开始，依次为1, 2,……直到N，N号牌在牌库底。为了发完所有的牌，荷官会进行N次发牌操作，在第i次发牌之前，他会连续进行R\_i次销牌操作，R\_i由输入给定。请问最后玩家拿到这副牌的顺序是什么样的？

举个例子，假设N = 4，则一开始的时候，牌库中牌的构成顺序为\{1, 2, 3, 4\}。

假设R1=2，则荷官应该连销两次牌，将1和2放入牌库底，再将3发给玩家。目前牌库中的牌顺序为\{4, 1, 2\}。

假设R2=0，荷官不需要销牌，直接将4发给玩家，目前牌库中的牌顺序为\{1,2\}。

假设R3=3，则荷官依次销去了1, 2, 1，再将2发给了玩家。目前牌库仅剩下一张牌1。

假设R4=2，荷官在重复销去两次1之后，还是将1发给了玩家，这是因为1是牌库中唯一的一张牌。

## Input ##

第1行，一个整数N，表示牌的数量。第2行到第N + 1行，在第i + 1行，有一个整数R\_i， 0≤R\_i<N

## Output ##

第1行到第N行：第i行只有一个整数，表示玩家收到的第i张牌的编号。

## Sample Input ##

4  
2  
0  
3  
2

## Sample Output ##

3  
4  
2  
1

## HINT ##

N<=70万

## Solution ##

一看是splay裸题就上splay硬艹结果因为人傻常数大只有80……于是换了线段树写法

开个线段树存一下每种牌的数量0/1  
在值域线段树上二分即可。  
代码简单易懂

最后面贴一下我GG的splay

## Code ##

1 #include<iostream>
     2 #include<cstdio>
     3 #define N  (700000+1000)
     4 using namespace std;
     5 
     6 int Segt[N<<2];
     7 
     8 inline int read()
     9 {
    10     int x=0,w=1; char c=getchar();
    11     while (!isdigit(c)&&c!='-') c=getchar();
    12     if (c=='-') c=getchar(),w=-1;
    13     while (isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
    14     return x*w;
    15 }
    16 
    17 void Build(int now,int l,int r)
    18 {
    19     if (l==r){Segt[now]=1; return;}
    20     int mid=(l+r)>>1;
    21     Build(now<<1,l,mid); Build(now<<1|1,mid+1,r);
    22     Segt[now]=Segt[now<<1]+Segt[now<<1|1];
    23 }
    24 
    25 void Update(int now,int l,int r,int k)
    26 {
    27     Segt[now]--;
    28     if (l==r){printf("%d\n",l); return;}
    29     int mid=(l+r)>>1;
    30     if (k<=Segt[now<<1]) Update(now<<1,l,mid,k);
    31     else Update(now<<1|1,mid+1,r,k-Segt[now<<1]);
    32 }
    33 
    34 int main()
    35 {
    36     int n,x,p=0;
    37     n=read();
    38     Build(1,1,n);
    39     for (int i=1; i<=n; ++i)
    40     {
    41         x=read();
    42         p=(p+x)%(n-i+1);
    43         Update(1,1,n,p+1);
    44     }
    45 }

1 #include<iostream>
     2 #include<cstdio>
     3 #define N (700000+1000)
     4 using namespace std;
     5 
     6 int n,x,Root,Father[N],Son[N][2],Size[N];
     7 
     8 void Update(int x){Size[x]=1+Size[Son[x][0]]+Size[Son[x][1]];}
     9 int Get(int x){
        return Son[Father[x]][1]==x;}
    10 
    11 inline int read()
    12 {
    13     int x=0,w=1;
    14     char c=getchar();
    15     while (!isdigit(c)&&c!='-') c=getchar();
    16     if (c=='-') c=getchar(),w=-1;
    17     while (isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
    18     return x*w;
    19 }
    20 
    21 void Build(int fa,int l,int r)
    22 {
    23     if (l>r) return;
    24     if (l==r) Size[l]=1;
    25     int mid=(l+r)>>1;
    26     Build(mid,l,mid-1);
    27     Build(mid,mid+1,r);
    28     Father[mid]=fa; Son[fa][mid>fa]=mid;
    29     Update(mid);
    30 }
    31 
    32 void Rotate(int x)
    33 {
    34     int wh=Get(x);
    35     int fa=Father[x],fafa=Father[fa];
    36     if (fafa) Son[fafa][Son[fafa][1]==fa]=x;
    37     Father[fa]=x; Son[fa][wh]=Son[x][wh^1];
    38     Father[x]=fafa; Son[x][wh^1]=fa;
    39     if (Son[fa][wh]) Father[Son[fa][wh]]=fa;
    40     Update(fa); Update(x);
    41 }
    42 
    43 void Splay(int x,int tar)
    44 {
    45     for (int fa; (fa=Father[x])!=tar; Rotate(x))
    46         if (Father[fa]!=tar)
    47             Rotate(Get(fa)==Get(x)?fa:x);
    48     if (!tar) Root=x;
    49 }
    50 
    51 int Findkth(int x)
    52 {
    53     int now=Root;
    54     while (1)
    55         if (Size[Son[now][0]]>=x) now=Son[now][0];
    56         else
    57         {
    58             x-=Size[Son[now][0]];
    59             if (x==1){
        /*Splay(now,0);*/ return now;}
    60             x--; now=Son[now][1];
    61         }
    62 }
    63 
    64 int Split(int l,int r)
    65 {
    66     int x=Findkth(l);
    67     int y=Findkth(r+2);
    68     Splay(x,0); Splay(y,x);
    69     return Son[y][0];
    70 }
    71 
    72 int main()
    73 {
    74     n=read();
    75     Build(0,1,n+2);
    76     Root=(n+3)>>1;
    77     for (int i=1; i<=n; ++i)
    78     {
    79         x=read();
    80         x%=n-i+1;
    81         if (x)
    82         {
    83             int now=Split(1,x);
    84             Son[Father[now]][Son[Father[now]][1]==now]=0;
    85             Father[now]=0;
    86             int fa=Split(n-i+1-x,n-i+1-x);
    87             Son[fa][1]=now; Father[now]=fa;
    88             Splay(now,0);
    89         }
    90         int now=Split(1,1); printf("%d\n",now-1);
    91         Son[Father[now]][0]=0;
    92         Father[now]=0; Update(Son[Root][1]);
    93     }
    94 }

转载于:https://www.cnblogs.com/refun/p/9236055.html