POJ 2886 单点更新

题意：n个小孩围一圈，他们手上卡片的数字代表下一个要出去的孩子，第K个孩子出去得到糖的数量是k的约数，输出得到糖最多的那个孩子的姓名和糖数。

首先要求反素数，也就是约数最多的，打表就行。然后线段树节点存放这个区间有多少个孩子还没走。然后模拟这个过程求出第P个孩子。

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define maxn 500005
int RPrime[]= //反素数
{
    1,2,4,6,12,24,36,48,60,120,180,240,360,720,840,1260,1680,2520,5040,7560,10080,15120,
    20160,25200,27720,45360,50400,55440,83160,110880,166320,221760,277200,332640,498960,
    554400
};
int fact[]= //反素数约数个数
{
    1,2,3,4,6,8,9,10,12,16,18,20,24,30,32,36,40,48,60,64,72,80,84,90,96,100,108,120,128,
    144,160,168,180,192,200,216
};
int node[maxn<<2];
struct child
{
    char name[15];
    int num;
} data[maxn];
void build(int rt,int l,int r)
{
    node[rt]=r-l+1;
    if(l==r)
    {
        node[rt]=1;
        return;
    }
    int mid=(r+l)>>1;
    build(rt<<1,l,mid);
    build(rt<<1|1,mid+1,r);
}
int updata(int rt,int l,int r,int k)
{
    node[rt]--;
    if(l==r)
    {
        return l;
    }
    int mid=(l+r)>>1;
    if(k<=node[rt<<1])
        return updata(rt<<1,l,mid,k);
    else
        return updata(rt<<1|1,mid+1,r,k-node[rt<<1]);
}
int main()
{
    int n,k,p;
    while(~scanf("%d%d",&n,&k))
    {
        for(int i=1; i<=n; i++)
            scanf("%s%d",data[i].name,&data[i].num);
        for(int i=0; RPrime[i]<=n; i++) p=i;
        build(1,1,n);
        for(int i=1; i<RPrime[p]; i++)
        {
            int luck=updata(1,1,n,k),mod=node[1];
            if(data[luck].num>0)
                k=((k+data[luck].num-2)%mod+mod)%mod+1;
            else k=((k+data[luck].num-1)%mod+mod)%mod+1;
        }
        printf("%s %d\n",data[updata(1,1,n,k)].name,fact[p]);
    }
    return 0;
}