# Who Gets the Most Candies? POJ - 2886（线段树单点更新+区间查询+反素数）

```  1 #include <iostream>
2 #include <cmath>
3 #include <cstdio>
4
5 #define ll long long
6
7 using namespace std;
8
9 const int N = 5e5+10;
10 struct Info{
11     char name[20];
12     int turn;
13 }p[N];
14 struct node{
15     int l,r,value;
16     int mid(){ return (l+r) >> 1; }
17 }tree[N << 2];
18 int c[N];
19 int n, s, ss, inx;
20 int pr[] = {2,3,5,7,11,13,17,19,23,29};
21 int Max,num;
22
23 void dfs(int inx, int v, int cnt, int pw){
24     for(int i = 1; i <= pw; ++i){
25         if((ll)v * pr[inx] > (ll)n){
26             if(Max < cnt * i){
27                 Max = cnt * i;
28                 num = v;
29
30             }else if(cnt * i == Max) num = min(num, v);
31             break;
32         }
33         else dfs(inx + 1, v *= pr[inx], cnt * (i + 1), i);
34
35     }
36 }
37
38 //反素数模板
39 void AntPrime(){
40     Max = 1;
41     dfs(0, 1, 1, 30);
42 }
43
44 void build_tree(int rt, int L, int R){
45     tree[rt].l = L; tree[rt].r = R;
46     if(L == R){
47         if(L == s) inx = rt;
48         tree[rt].value = 1;
49         return;
50     }
51     int mid = tree[rt].mid();
52     int lson = rt << 1;
53     int rson = rt << 1 | 1;
54     build_tree(lson, L, mid);
55     build_tree(rson,mid + 1, R);
56     tree[rt].value = tree[lson].value + tree[rson].value;
57 }
58
59 void update(int x){
60     while(x != 1){
61         --tree[x].value;
62         x >>= 1;
63     }
64 }
65
66 void search(int tot,int rt){
67     //找到位置
68     if(tree[rt].l == tree[rt].r){
69         ss = tree[rt].l; //原始队列的位置
70         inx = rt; //线段树的位置，方便更新
71         return;
72     }
73     int lson = rt << 1;
74     int rson = rt << 1 | 1;
75     if(tree[lson].value >= tot) search(tot, lson);
76     else search(tot - tree[lson].value, rson);
77 }
78
79 void solve(){
80     while(~scanf("%d%d", &n, &s)){
81         build_tree(1,1,n);
82         AntPrime();//得到反素数和它的约数个数
83         for(int i = 1; i <= n; ++i){
84             scanf("%s%d", p[i].name, &p[i].turn);
85         }
86         int cnt = 0;
87         int remain = n;
88         //s  淘汰队列人的位置
89         //ss 原始队列人的位置
90         ss = s;
91         while(++cnt != num){
92             update(inx);//更新线段树
93             int turn = abs((double)p[ss].turn);
94             turn %= (remain - 1);
95             if(!turn) turn = remain - 1;
96             if(p[ss].turn > 0){
97                 int r = remain - s;
98                 if(r >= turn) s = s + turn - 1;
99                 else s = turn - r;
100             }else{
101                 int l = s - 1;
102                 if(l >= turn) s = l - turn + 1;
103                 else s = (remain - 1) - (turn - l) + 1;
104             }
105             // cout << "position is " << ss << endl;
106             // cout << "jumped out people  " << p[ss].name << endl;
107             search(s, 1);
108             --remain;
109         }
110         printf("%s %d\n", p[ss].name, Max);
111     }
112 }
113
114 int main(){
115
116     solve();
117
118     return 0;
119 }
```