bzoj 4415: [Shoi2013]发牌

.

题意：一沓牌从1到n，每次把$r_i$张牌从牌堆顶放到牌堆底，然后发出牌堆顶的牌。求发牌顺序。
题解：二分+树状数组。树状数组记录到某个位置有几张牌，然后每次记录现在是第几张牌。二分找出位置然后再更新就好了。$O(nlog^2n)$好慢。。。
代码：

#include<cstdio>
#include<cstring>

int n,s[700010];//存在几张牌

int lb(int x)
{
    return x&-x;
}
void add(int x,int y)
{
    for(int i=x;i<=n;i+=lb(i))
    s[i]+=y;
}
int get(int x)
{
    int ans=0;
    for(int i=x;i>0;i-=lb(i))
    ans+=s[i];
    return ans;
}
int fd(int x)
{
    int l=1,len=n;
    while(len)
    {
        int md=l+(len>>1);
        if(get(md)<x)
        {
            l=md+1;
            len=len-(len>>1)-1;
        }
        else
        len>>=1;
    }
    return l;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    add(i,1);
    int now=0;
    for(int i=1;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        x=x%(n+1-i);
        now=(now+x)%(n+1-i);
        int hh=fd(now+1);
        printf("%d\n",hh);
        add(hh,-1);
    }
}