POJ 2886 Who Gets the Most Cadies？線分ツリーの変更】

Who Gets the Most Cadies？
http://poj.org/problem?id=2886
Time Limit: 5000 MS
 
メモリLimit: 131313722 K
Total Submissions: 161635
 
Acceepted: 5298
Case Time Limit: 2000 MS
Description
N children are sitting in a circele to Playa game.
The children are numberd from 1 to N in clockwise order.Each of them has a card with a non-ゼロinteger on it in his/her hand.The game starts from the K-th child、who tells the others the integer on his card and jump out of the circule.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 jumed out of the circule.During the game，the p-th child juming 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
The re 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 line a s contains the names of the children（consisting of at most 10 letters）and the integers（non-zerwith magnitudes with in 108）on their cards increase order of the children’s numbers，a name and intega paradie e e e e e parading.parading.parading.parading.parading.spres。
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 chose the child who jum of the circe firs.
Sample Input

4 2
Tom 2
Jack 4
Mary -1
Sam 1

Sample Output

Sam 3

ソurce
POJ Monthly-20.07.30、Sempr
題意
 n人の子供は時計回りに配列しています。各人の手にはカードがあります。カードには数字があります。k番目の子供からチームを出発します。子供のカードには数字がvalで、彼から時計回りのval人には次のチームがあります。負の数は反時計回りの数のあのval番目の人で、P番目のチームが出るともらえるキャンディの数はpの因子の数です。一番多くのキャンディを出力した人と彼のキャンディの数は、複数があれば、一番先に出る人を出力します。
考え方
まず表を打って1-500000の因子の個数を求めて、それから線分の木を使って、点は改正して、区間の情報はこの区間のためにまだ何人残っていますか？
C++コード

#include

using namespace std;

#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1

const int N=500050;

char name[N][15];
int val[N];
int f[N];//f[i]=j，   i j    
int sum[N<<2];

//   f[n] 
void maketable(int n)
{
	for(int i=1;i>1;
	build(ls);
	build(rs);
	pushup(rt);
}

int update(int num,int l,int r,int rt)
{
	if(l==r)
	{
		sum[rt]=0;
		return l;
	}
	int m=(l+r)>>1;
	int res;
	if(num<=sum[rt<<1])
	  res=update(num,ls);
	else
	  res=update(num-sum[rt<<1],rs);
	pushup(rt);
	return res;
}

int main()
{
	int n,k;
	maketable(N);
	while(~scanf("%d%d",&n,&k))
	{
		for(int i=1;i<=n;i++)
		  scanf("%s%d",name[i],&val[i]);
		  
		build(1,n,1);
		int order=getorder(n);//      order           
		
		int pos=0,num=k,total=n,ln=0,rn=0;
		
		for(int i=1;i<=order;i++)
		{
			pos=update(num,1,n,1);
			total--;
			ln=num-1;//            
			rn=total-num+1;//           
			if(i==order) break;//   order     ，  
			//                 num  ，  num 
			int v=val[pos];//v      
			if(v>0)
			{
				v%=total;
				if(!v) v=total;
				if(v<=rn)
				  num=ln+v;
				else
				  num=v-rn;
			} 
			else
			{
				v=-v;
				v%=total;
				if(!v) v=total;
				if(v<=ln)
				  num=ln-v+1;
				else
				  num=total-v+ln+1;
			}
		}
		printf("%s %d
",name[pos],f[order]); 
	}
	return 0;
}