POJ 2886 线段树单点更新

转载自：http://blog.csdn.net/sdj222555/article/details/6878651

反素数拓展参照：http://blog.csdn.net/ACdreamers/article/details/25049767

题目大意就是一群熊孩子做游戏，第一个出队的人是编号为k的人。此后出队的人就是按照前一个人手里的编号。如果是正数+m就是这个人的左边的第m个人。如果是负数-m,就是这个人的右边第m个人。由于这个人出队了。对下一个人有影响，所以+m的时候，是k+m-1。-m的时候是k+m。因为是他后边的人所以没有影响。因为可能出现负数和0的情况，所以就有下面的取模时的处理。线段树的每个节点保存的是这个区间还有多少个位置。所以每次更新时，如果左孩子节点的空位够了，搜索左孩子，否则搜索右孩子。可以建树参照对样例模拟一下。

还不懂怎么打反素数表。所以是cooy的。

附代码：

 #include <stdio.h>

 #include <string.h>

 #include <iostream>

 using namespace std;

 #define lson l, m, rt<<1

 #define rson m+1, r, rt<<1|1

 #define N 500010

 int tree[N<<];

 const int antiprime[] = { // 反素数表

     ,,,,,,,,,,,,,,,

     ,,,,,,,,,

     ,,,,,,,,

     ,,,,

 };

 const int factorNum[] = { // 对应的约数个数

     ,,,,,,,,,,,,,,,,,,,

     ,,,,,,,,,,,,,,

     ,,,

 };

 struct child{  // 保存输入时的节点信息

     char name[];

     int val;

 }c[N];

 void Build(int l, int r, int rt) {  // 建树

    tree[rt] = r-l+;

    if (l == r)

    return;

    int m = (l+r)>>;

    Build(lson);

    Build(rson);

 }

 int Update(int p, int l, int r, int rt) {  // 第p个人出去。Update函数可以理解。

     tree[rt]--;

     if (l == r)

     return r;

     int m = (l+r)>>;

     if (p<=tree[rt<<])

     return Update(p, lson);

     else return Update(p-tree[rt<<], rson);

 }

 int main() {

    int i, n, &mod = tree[];

    // mod 保存的就是一共有多少个人、

    int k;

    while(~scanf("%d%d", &n, &k)) {

      // 输入建树

      for (i=; i<=n; ++i) {

         scanf("%s%d", c[i].name, &c[i].val);

      }

      Build(, n, );

      // 小于等于n的最大的反素数。

      int cnt = ;

      while(cnt <  && antiprime[cnt] <= n) {

         cnt++;

      }

      cnt--;

      // 先找到1-n范围内的约束个数最大的数。

      // pos是记录当前位置该出队的人的ID

      int pos = ;

      c[pos].val = ;

      // 找antiprime[cnt]出队的人的名字、

      for (i=; i<antiprime[cnt]; ++i) {  // 循环的次数就是直到这个人出队。

         // 这两个if是根据 这个人手里牌的编号来推算下一个出队列的人的当前位置、

         if (c[pos].val > )

         k = ((k+c[pos].val-)%mod+mod)%mod+;

         else k=((k+c[pos].val-)%mod+mod)%mod+;

        // pos 记录的是当前循环出队的人的所在位置、

         pos = Update(k, , n, );

         cout << pos << "====\n";

      }

      printf("%s %d\n", c[pos].name, factorNum[cnt]);

    }

    return ;

 }

巴特西

POJ 2886 线段树单点更新

最新文章

热门文章