poj 2886 Who Gets the Most Candies? （線段樹單點更新應用）

poj 2886 Who Gets the Most Candies?

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 10⁸) 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 個小孩圍成一圈，他們被順時針編號為 1 到 N。每個小孩手中有一個卡片，上面有一個非 0 的數字，游戲從第 K 個小孩開始，他告訴其他小孩他卡片上的數字並離開這個圈，他卡片上的數字 A 表明了下一個離開的小孩，如果 A 是大於 0 的，則下個離開的是左手邊第 A 個，如果是小於 0 的，則是右手邊的第 -A 個小孩。游戲將直到所有小孩都離開，在游戲中，第 p 個離開的小孩將得到 F(p) 個糖果，F(p) 是 p 的約數的個數，問誰將得到最多的糖果。輸出最幸運的小孩的名字和他可以得到的糖果。

解題思路：建樹：節點存的是他所包含的葉結點個數。

更新樹：用於刪除葉結點。

反素數：打表。

#include
#include
int antiprime[]={//反素數
	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 factor[]={//反素數約數個數
	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
};
const int N = 500005 * 4;
int S[N], V[N], L[N], R[N];
void build(int u, int l, int r) {
	L[u] = l;
	R[u] = r;
	S[u] = r - l + 1;
	if (l == r) {
		return;
	}
	int mid = (l + r) / 2;
	build(u * 2, l, mid);
	build(u * 2 + 1, mid + 1, r);
}
int modify(int u, int x) {
	S[u]--;
	if (L[u] == R[u]) {
		return L[u];
	}
	if (S[u * 2] >= x) {
		return modify(u * 2, x);      
	}
	else {
		return modify(u * 2 + 1, x - S[u * 2]);     //如果所查結點不在左子樹中，除掉在左子樹種的部分，其余的部分在右子樹中查找
	}
}
char name[N][50];
int num[N];
int main() {
	int n, k;
	while (scanf("%d%d", &n, &k) == 2) {
		for (int i = 1; i <= n; i++) {
			scanf("%s%d", name[i], &num[i]);
		}
		build(1, 1, n);
		int cnt = 0;
		while (antiprime[cnt] <= n) cnt++;
		cnt--;
		int cnt2 = 0;  
		num[cnt2] = 0;  
		for(int i = 0; i < antiprime[cnt]; i++)  
		{  
			if(num[cnt2] > 0)  
			{  
				k = ((k + num[cnt2] - 2) % S[1] + S[1]) % S[1] + 1;     //"-2“一是因為刪除了之前的結點，所以往前移，一是因為要刪除本節點，所以向前移
                                                                                                         //第一個() % S[1] 是當num[cnt2]太大時，把它除回來。後面的  +S[1]) % S[1]是考慮負數的情況，最後+1歸位  
                         }  
			else  
			{  
				k = ((k + num[cnt2] - 1) % S[1] + S[1]) % S[1] + 1;  
			}  
			cnt2 = modify(1, k);  
		}  
		printf("%s %d\n", name[cnt2], factor[cnt]);  
	}
	return 0 ;
}