POJ 2886（线段树+单点修改+约瑟夫环）

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 Ais 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

n个孩子按顺时针排列，每个人手上都有一张牌，牌上有一个数字，从第k个孩子开始出队，出队的孩子卡上数字是val,则从他开始顺时针第val人是下一个出队的，负数则逆时针数那个第val个人，第P个出队的会得到的糖果数是p的因子个数，输出得到最多糖果的人和他的糖果数，如果有多个，则输出最先出队的人。

  其实本题就是模拟每轮游戏，然后在每一轮游戏中先算出当前需要出队的第j个孩子，然后用线段树找到还在队中的第j个还是得原始编号。

        首先建立一棵线段树，其每个叶节点都是1（代表每个孩子都在圈中，如果第i个孩子不在圈中，那么就令第i个叶子（孩子的编号不是i而是i管理的区间l或r）sum=0）。

分析题中的例子：

4 2

Tom 2

Jack 4

Mary -1

Sam 1

       假设我们第一个出去的孩子是第2个孩子，那么我们把第二个叶节点的值置为0，该步只需要通过update找到sum值正好为2的那个区间的右端点（且该右端点的sum值也为1）即可。然后让这个sum变为0，表示这个孩子出了圈。并且我们读到了JACK的val值为4，当前圈剩余3个人，所以我们向后找4%3=1个人，如果[3，n]内的sum和>=1，那么直接在JACK右边即[3，n]区间找即可。如果sum的和<1，那么就在JACK左边[1,1]内找1-sum的那个位置的1.

       依次类推即可。线段树的每个叶节点维护name，val，sum三个值，非叶节点只需要维护sum值即可。

AC代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stdlib.h>
#include<queue>
#include<set>
#include<iomanip>
#include<math.h>
using namespace std;
typedef long long ll;
typedef double ld;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
#define MAX_N 500100
int s[MAX_N];
int bit[MAX_N];
int id[MAX_N];
char name[MAX_N][12];
int N,K;

void init()
{
    int i,j,k,m;
    for(i=0; i<MAX_N; i++)
        s[i]=1;
    for(i=2; i<=MAX_N; i++)
    {
        if(s[i]==1)
        {
            for(j=i; j<=MAX_N; j+=i)
            {
                k=0;
                for(m=j; m%i==0; m/=i,k++);
                s[j]*=k+1;
            }
        }
    }
}

void add(int i,int x)
{
    while(i<=N)
    {
        bit[i]+=x;
        i+=i&-i;
    }
}
int query(int i)
{
    int sum=0;
    while(i>0)
    {
        sum+=bit[i];
        i-=i&-i;
    }
    return sum;
}

int find(int x)
{
    int l,r,m;
    l=1;
    r=N;
    while(l<r)
    {
        m=(l+r)/2;
        if(query(m)<x)
            l=m+1;
        else
            r=m;
    }
    return l;
}

int main(void)
{
    int i,num,max,pos,p,lo;
    init();
    while(~scanf("%d%d",&N,&K))
    {
        num=N;
        for(i=1; i<=N; i++)
            scanf("%s%d",name[i],&id[i]);
        for(i=1; i<=N; i++)
            add(i,1);
        max=-1;
        for(i=2; i<=N; i++)
            if(max<s[i])
            {
                max=s[i];
                pos=i;
            }
        lo=K;

        while(--pos)
        {
            add(lo,-1);
            num--;
            if(id[lo]>0)
                K=((K-2+id[lo])%num+num)%num+1;
            else
                K=((K-1+id[lo])%num+num)%num+1;
            lo=find(K);
        }
        printf("%s %d\n",name[lo],max);
    }
    return 0;
}