首页 > 代码库 > 【POJ】Buy Tickets（线段树）

【POJ】Buy Tickets（线段树）

2024-07-14 23:51:21   221人阅读

点更新用法很巧妙的一道题。倒序很容易的找到该人的位置，而update操作中需要不断的变化下标才能合理的插入。看了别人写的代码，学习了。

 

 1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <map> 5 using namespace std; 6  7 const int maxn = 2e5 + 10; 8 int sumv[maxn << 2], data[maxn]; 9 10 void PushUp (int rt) {11     sumv[rt] = sumv[rt << 1] + sumv[rt << 1 | 1];12 }13 14 void build (int l, int r, int rt) {15     if (l == r) {16         sumv[rt] = 1;17         return ;18     }19     int m = (l + r) / 2;20     build (l, m, rt << 1);21     build (m + 1, r, rt << 1 | 1);22     PushUp (rt);23 }24 25 void update (int p, int v, int l, int r, int rt) {26     if (l == r) {27         data[l] = v; sumv[rt] = 0;28         return ;29     }30     int m = (l + r) >> 1;31     if (sumv[rt * 2] >= p) {32         update (p, v, l, m, rt * 2);33     } else {34         update (p - sumv[rt * 2], v, m + 1, r, rt * 2 + 1);35     }36     PushUp(rt);37 }38 39 int main () {40     pair<int, int> p[maxn];41     int n;42     while (~scanf ("%d", &n)) {43         for (int i = 0; i < n; ++ i) {44             scanf ("%d%d", &p[i].first, &p[i].second);45         }46         build (1, n, 1);47         for (int i = n - 1; i >= 0; -- i) {48             update (p[i].first + 1, p[i].second, 1, n, 1);49         }50         for (int i = 1; i <= n; ++ i) {51             if (i == 1) {52                 printf ("%d", data[i]);53             } else {54                 printf (" %d", data[i]);55             }56         }57         puts("");58     }59     return 0;60 }

 


联系
我们