HDU 2886 線段樹單點修改

傳送門：點選打開連結

Who Gets the Most Candies?

Time Limit: 5000MS	Memory Limit: 131072K
Total Submissions: 10852	Accepted: 3371
Case Time Limit: 2000MS

Description

N children are sitting in a circle to play a game.

The children are numbered from 1 to N in clockwise order. Each of them has a card with a non-zero integer on it in his/her hand. The game starts from the K-th child, who tells all the others the integer on his card and jumps out of the circle. The integer on his card tells the next child to jump out. Let A denote the integer. If A is positive, the next child will be the A-th child to the left. If A is negative, the next child will be the (−A)-th child to the right.

The game lasts until all children have jumped out of the circle. During the game, the p-th child jumping out will get F(p) candies where F(p) is the number of positive integers that perfectly divide p. Who gets the most candies?

Input

There are several test cases in the input. Each test case starts with two integers N (0 < N ≤ 500,000) and K (1 ≤ K ≤ N) on the first line. The next N lines contains the names of the children (consisting of at most 10 letters) and the integers (non-zero with magnitudes within 108) on their cards in increasing order of the children’s numbers, a name and an integer separated by a single space in a line with no leading or trailing spaces.

Output

Output one line for each test case containing the name of the luckiest child and the number of candies he/she gets. If ties occur, always choose the child who jumps out of the circle first.

Sample Input

4 2
Tom 2
Jack 4
Mary -1
Sam 1      

Sample Output

Sam 3      

Source

POJ Monthly--2006.07.30, Sempr

題意：有n個熊孩子站成一圈玩遊戲，順時針編号從1~n。他們每個人有一個數字（不為0），當第i個人出圈的時候，如果他的數為正數x，則下一個出圈的是從這個人開始（這個人不算）順時針數的第xi個人。為負數則是逆時針。第i個出圈的熊孩子獲得i的因子的個數個糖果。問獲得糖果最多的最先出圈的是誰。

思路：用線段樹記錄區間内剩餘的人數。譬如查找第x個人，如果左區間的人數小于等于x,就遞歸到左區間，否則就遞歸到右區間尋找第x-(左區間人數)個人。傳回其最初的編号。用k記錄實際是第幾個人出圈，當這個人手裡為正數的時候，他出圈了，那麼後面人的時間編号都會減1，這裡要十分地注意！

代碼：

#include<cstdio>
#include<cstring>
int sum[2000005];
char name[500005][12];
int num[500005];
int tmp[500005];
int ans;
void init(int n=500000)
{
    memset(tmp,0,sizeof(tmp));
    for(int i=1;i<=n;i++)
    for(int j=i;j<=n;j+=i) tmp[j]++;
}
void init2(int n)
{
    ans=0;
    for(int i=1;i<=n;i++) if(ans<tmp[i]) ans=tmp[i];
}
void build(int id,int L,int R)
{
    sum[id]=R-L+1;
    if(L==R) return;
    else
    {
        int mid=(L+R)>>1;
        build(id<<1,L,mid);
        build(id<<1|1,mid+1,R);
    }
}
int que(int id,int L,int R,int c)
{
    if(L==R)
    {
        sum[id]--;
        return L;
    }
    else
    {
        sum[id]--;
        int mid=(L+R)>>1;
        if(c<=sum[id<<1]) return que(id<<1,L,mid,c);
        else return que(id<<1|1,mid+1,R,c-sum[id<<1]);
    }
}
int main()
{
    init();
    int n,k;
    while(~scanf("%d %d",&n,&k))
    {
        init2(n);
        for(int i=1;i<=n;i++)
        {
            scanf("%s %d",name[i],&num[i]);
        }
        build(1,1,n);
        int pos=k;
        for(int i=1;i<=n;i++)
        {
            pos=que(1,1,n,k);
            if(tmp[i]==ans)
            {
                printf("%s %d\n",name[pos],ans);
                break;
            }
            if(num[pos]>0)
            {
                k=(k-1+num[pos]-1)%(n-i)+1;
            }
            else
            {
                k=((k-1+num[pos])%(n-i)+(n-i))%(n-i)+1;
            }
        }
    }
    return 0;
}