POJ 2886.Who Gets the Most Candies? -线段树(单点更新、类约瑟夫问题)

Mike

线段树可真有意思呢续集2。。。
区间成段的替换和增减，以及区间求和等，其中夹杂着一些神奇的操作，数据离散化，简单hash，区间异或，还需要带着脑子来写题。
有的题目对数据的操作并不是直接按照题面意思进行操作，而是换一个角度，通过对其他数据的操作得到结果，感觉真的是。。。啊啊啊啊啊啊，我的脑子离家出走了，他在哪啊(ಥ_ಥ)ru
写到后面的题目就感觉满满的都是套路，只要想到怎样处理数据以及如果通过线段树维护数据就可以，但是就是这个是关键(废话。。。)，嘤嘤嘤，一拳一个嘤嘤怪，好好写题解。。。
POJ2886.Who Gets the Most Candies?
这个题可以偷懒一下，先找出n个数中第几个数的小孩能得到最多的糖果，for循环跑一遍找出来最大的h，很多人是用反素数写的因数个数，然而，并没有懂，直接跑一遍for就可以的吧。。。
然后只需要对线段树进行h次操作就可以了。因为每次操作的pos不确定，所以需要实时更新pos，取模的mod也是实时变化的，但是tree[1]中存了这个值，所以直接每次操作完重新给mod赋值tree[1]就可以。因为分向左还是向右，所以操作要注意。我就是这里出了问题。关于约瑟夫问题，具体的不介绍，自行百度吧。
这个题和插队的问题差不多，都需要带着脑子写，这些应该都是经典的线段树的题目吧。
好菜啊，为什么我这么菜。。。
代码:

1 //F
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<algorithm>
 7 #include<cstdlib>
 8 #include<queue>
 9 #include<stack>
10 using namespace std;
11 typedef long long ll;
12 const int inf=0x3f3f3f3f;
13 const double eps=1e-5;
14 const int maxn=5*1e5+10;
15 #define lson l,m,rt<<1
16 #define rson m+1,r,rt<<1|1
17 struct node{
18   char na[10];
19   int num;
20 }a[maxn];
21 int tree[maxn<<2],ans[maxn];
22 int n,time;
23 void init()
24 {
25   memset(ans,0,sizeof(ans));
26   int cnt=(int)sqrt(n*1.0);
27   for(int i=1;i<=cnt;i++)
28   {
29     for(int j=i+1;j*i<=n;j++)
30       ans[j*i]+=2;
31     ans[i*i]++;
32   }
33   int maxx=ans[1];
34   time=1;
35   for(int i=2;i<=n;i++)
36   {
37     if(ans[i]>maxx)
38     {
39       maxx=ans[i];
40       time=i;
41     }
42   }
43 }
44 void build(int l,int r,int rt)
45 {
46   tree[rt]=r-l+1;
47   if(l==r){
48     return ;
49   }
50 
51   int m=(l+r)>>1;
52   build(lson);
53   build(rson);
54 }
55 int update(int pos,int l,int r,int rt)
56 {
57   tree[rt]--;
58   if(l==r){
59     return l;
60   }
61 
62   int m=(l+r)>>1;
63   if(pos<=tree[rt<<1]) return update(pos,lson);
64   else return update(pos-tree[rt<<1],rson);
65 }
66 int main()
67 {
68   int k,mod;
69   while(~scanf("%d%d",&n,&k))
70   {
71     init();
72     for(int i=1;i<=n;i++)
73       scanf("%s%d",&a[i].na,&a[i].num);
74     build(1,n,1);
75     int pos=0;a[pos].num=0;
76     mod=tree[1];
77     int h=time;
78     while(h--)
79     {
80       if(a[pos].num>0)
81         k=((k-1+a[pos].num-1)%mod+mod)%mod+1;
82       else
83         k=((k-1+a[pos].num)%mod+mod)%mod+1;
84       pos =update(k,1,n,1);
85       mod=tree[1];
86     }
87     printf("%s %d\n",a[pos].na,ans[time]);
88   }
89   return 0;
90 }