BZOJ 4415 发牌

线段树就好了啊。

为什么一眼splay啊。。。

其实splay也能过，但是线段树更方便？

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 700500
using namespace std;
int n,r,root,tot=0,ls[maxn<<2],rs[maxn<<2],val[maxn<<2],now;
void build(int &now,int left,int right)
{
    now=++tot;val[now]=right-left+1;
    if (left==right) return;
    int mid=(left+right)>>1;
    build(ls[now],left,mid);
    build(rs[now],mid+1,right);
    return;
}
int query(int now,int left,int right,int x)
{
    val[now]--;
    if (left==right) return left;
    int mid=(left+right)>>1;
    if (val[ls[now]]>=x) return query(ls[now],left,mid,x);
    else return query(rs[now],mid+1,right,x-val[ls[now]]);
}
int main()
{
    scanf("%d",&n);
    build(root,1,n);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&r);
        now=(now+r)%(n-i+1);
        printf("%d
",query(root,1,n,now+1));
    }
    return 0;
}