poj2886（线段树求序列第k小）

题目链接：https://vjudge.net/problem/POJ-2886

题意：n个人围成一个圈，每个人有姓名s和权值val两个属性，第一轮序号为k的人退出，并根据其val指定下一个人，val为正即其右第val个人，val为负及其左第val个人。求第p个出局的人的姓名，其中p的约数最多，并输出约数的数量。

思路：首先是数学问题，可通过唯一分解定理或筛法打表计算出n个人时第几个出局的人的约数最多f1[n]，和约数的数量f2[n]，数据很小，不打表的话会超时。然后进行f1[n]次循环，每次找出当前序列中第k小的人。利用线段树来实现，线段树的结点属性sum表示该区间剩余数的个数，每次更新时都要减一。最后就是确定每次的k值。

　　            if(tmp>0)
　　                k=((k-1+tmp-1)%Mod+Mod)%Mod+1;
　　            else
　　                k=((k+tmp-1)%Mod+Mod)%Mod+1;
tmp>0时，因为要将k删除，那么k的下一位仍是第k小，所以要减1，后面的减一再加一是避免出现0。tmp<0时，k的下一位是第k-1小，就不用减1了。自己举个例子模拟一下就懂了。

AC代码：

#include<cstdio>
using namespace std;
const int maxn=500005;

struct node1{
    char s[12];
    int val;
}boy[maxn];

struct node2{
    int l,r,sum;
}tr[maxn<<2];

int f1[40]={0,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,500001};
int f2[40]={0,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};
int n,k;

void build(int v,int l,int r){
    tr[v].l=l,tr[v].r=r,tr[v].sum=r-l+1;
    if(l==r) return;
    int mid=(l+r)>>1;
    build(v<<1,l,mid);
    build(v<<1|1,mid+1,r);
}

int update(int v,int k){
    --tr[v].sum;
    if(tr[v].l==tr[v].r)
        return tr[v].r;
    if(tr[v<<1].sum>=k) return update(v<<1,k);
    else return update(v<<1|1,k-tr[v<<1].sum);
}

int main(){
    while(~scanf("%d%d",&n,&k)){
        for(int i=1;i<=n;++i)
            scanf("%s%d",boy[i].s,&boy[i].val);
        int num,nump,nw=0,Mod=n,pos;
        for(int i=1;i<=39;++i)
            if(n>=f1[i]&&n<f1[i+1]){
                num=f1[i];
                nump=f2[i];
                break;
            }
        build(1,1,n);
        while(1){
            --Mod;
            pos=update(1,k);
            if(++nw==num) break;
            int tmp=boy[pos].val;
            if(tmp>0) 
                k=((k-1+tmp-1)%Mod+Mod)%Mod+1;
            else
                k=((k+tmp-1)%Mod+Mod)%Mod+1;
        }
        printf("%s %d
",boy[pos].s,nump);
    }
    return 0;
}