1 #include <cstdio>
2 #include <cstring>
3 #define lson l, m, rt << 1
4 #define rson m+1, r, rt << 1 | 1
5
6 const int MAX_N = 500000 + 10;
7 int sum[MAX_N << 2];
8 struct node
9 {
10 char name[15];
11 int val;
12 }boy[MAX_N<<2];
13 int ans[MAX_N];
14 int id;
15 int n, k;
16
17 void build(int l, int r, int rt)
18 {
19 sum[rt] = r - l + 1;
20 if (l == r)
21 return ;
22 int m = (l + r) >> 1;
23 build (lson);
24 build (rson);
25 }
26
27 int update(int p, int l, int r, int rt)
28 {
29 sum[rt]--;
30 if (l == r)
31 {
32 return l;
33 }
34 int m = (l + r) >> 1;
35 if (p <= sum[rt<<1])
36 {
37 return update (p, lson);
38 }
39 else
40 {
41 return update (p - sum[rt<<1], rson);
42 }
43 }
44
45 void Solve(){ //计算ans
46 memset(ans,0,sizeof(ans));
47 for(int i=1;i<=n;i++){
48 ans[i]++;
49 for(int j=2*i;j<=n;j+=i)
50 ans[j]++;
51 }
52 int max=ans[1];
53 id=1;
54 for(int i=2;i<=n;i++) //找出第几个人跳出获得的糖最多
55 if(ans[i]>max){
56 max=ans[i];
57 id=i;
58 }
59 }
60
61 int main(void) //POJ 2886 Who Gets the Most Candies?
62 {
63 //freopen ("inF.txt", "r", stdin);
64
65 while (~scanf ("%d%d", &n, &k))
66 {
67 build (1, n, 1);
68 for (int i=1; i<=n; ++i)
69 {
70 scanf ("%s%d", &boy[i].name, &boy[i].val);
71 //printf ("%s%d
", boy[i].name, boy[i].val);
72 }
73 Solve();
74 //int maxn = f(n);
75 int mod = sum[1];
76 boy[0].val = 0;
77 int pos = 0;
78 //printf ("%d
", id);
79 int m=id;
80 while (m--)
81 {
82 if (boy[pos].val > 0)
83 k=((k-1+boy[pos].val-1)%mod+mod)%mod+1;
84 else
85 k=((k-1+boy[pos].val)%mod+mod)%mod+1;
86 pos = update (k, 1, n, 1);
87 //printf ("%d ", pos);
88 mod = sum[1];
89 }
90 printf ("%s %d
", boy[pos].name, ans[id]);
91 }
92 }
线段树(单点更新) POJ 2886 Who Gets the Most Candies?
编译人生，运行世界！