题目描述

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}。
假设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万

题目分析

开一颗权值线段树记录区间size 记录堆顶是第几个,每次找第k个删掉即可

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,tot,root;
struct your
{
    int size,lson,rson;
}a[700000*20];
void update(int l,int r,int dx,int &x)
{
    if(!x) x=++tot;
    if(l==r) { a[x].size=1; return ; }
    int mid=(l+r)>>1;
    if(dx<=mid) update(l,mid,dx,a[x].lson);
    else update(mid+1,r,dx,a[x].rson);
    a[x].size=(a[a[x].lson].size+a[a[x].rson].size);
}
int del(int l,int r,int dx,int x)
{
    a[x].size--;
    if(l==r) return l;
    int mid=(l+r)>>1;
    if(a[a[x].lson].size>=dx) return del(l,mid,dx,a[x].lson);
    else return del(mid+1,r,dx-a[a[x].lson].size,a[x].rson);
}   
int main()
{   
    scanf("%d",&n);
    for(int i=1;i<=n;i++) update(1,n,i,root);
    int now=1,k=n;
    for(int x,i=1;i<=k;i++)
    {
        scanf("%d",&x);
        now=(now+x-1)%n+1;
        printf("%d\n",del(1,k,now,root));
        n--;
    }
    return 0;
}