POJ 3667 线段树

链接：

代码：

  1 #include <map>
  2 #include <set>
  3 #include <cmath>
  4 #include <queue>
  5 #include <stack>
  6 #include <cstdio>
  7 #include <string>
  8 #include <vector>
  9 #include <cstdlib>
 10 #include <cstring>
 11 #include <sstream>
 12 #include <iostream>
 13 #include <algorithm>
 14 #include <functional>
 15 using namespace std;
 16 #define rep(i,a,n) for (int i=a;i<n;i++)
 17 #define per(i,a,n) for (int i=n-1;i>=a;i--)
 18 #define all(x) (x).begin(),(x).end()
 19 #define pb push_back
 20 #define mp make_pair
 21 #define lson l,m,rt<<1  
 22 #define rson m+1,r,rt<<1|1 
 23 typedef long long ll;
 24 typedef vector<int> VI;
 25 typedef pair<int, int> PII;
 26 const ll MOD = 1e9 + 7;
 27 const int INF = 0x3f3f3f3f;
 28 const int MAXN = 5e4 + 7;
 29 // head
 30 
 31 int cover[MAXN << 2];
 32 int lsum[MAXN << 2], rsum[MAXN << 2], msum[MAXN << 2];
 33 
 34 void pushup(int rt, int m) {
 35     lsum[rt] = lsum[rt << 1], rsum[rt] = rsum[rt << 1 | 1];
 36     if (lsum[rt << 1] == m - (m >> 1)) lsum[rt] += lsum[rt << 1 | 1];
 37     if (rsum[rt << 1 | 1] == m >> 1) rsum[rt] += rsum[rt << 1];
 38     msum[rt] = max(max(msum[rt << 1], msum[rt << 1 | 1]), rsum[rt << 1] + lsum[rt << 1 | 1]);
 39 }
 40 
 41 void pushdown(int rt, int m) {
 42     if (cover[rt] != -1) {
 43         cover[rt << 1] = cover[rt << 1 | 1] = cover[rt];
 44         lsum[rt << 1] = rsum[rt << 1] = msum[rt << 1] = (cover[rt] ? 0 : m - (m >> 1));
 45         lsum[rt << 1 | 1] = rsum[rt << 1 | 1] = msum[rt << 1 | 1] = (cover[rt] ? 0 : m >> 1);
 46         cover[rt] = -1;
 47     }
 48 }
 49 
 50 void build(int l, int r, int rt) {
 51     cover[rt] = -1;
 52     lsum[rt] = rsum[rt] = msum[rt] = r - l + 1;
 53     if (l == r) return;
 54     int m = (l + r) >> 1;
 55     build(lson);
 56     build(rson);
 57 }
 58 
 59 void update(int L, int R, int x, int l, int r, int rt) {
 60     if (L <= l && r <= R) {
 61         cover[rt] = x;
 62         lsum[rt] = rsum[rt] = msum[rt] = (x ? 0 : r - l + 1);
 63         return;
 64     } 
 65     pushdown(rt, r - l + 1);
 66     int m = (l + r) >> 1;
 67     if (L <= m) update(L, R, x, lson);    
 68     if (R > m) update(L, R, x, rson);
 69     pushup(rt, r - l + 1);
 70 }
 71 
 72 int query(int x, int l, int r, int rt) {
 73     if (l == r) return l;
 74     pushdown(rt, r - l + 1);
 75     int m = (l + r) >> 1;
 76     if (msum[rt << 1] >= x) return query(x, lson);
 77     else if (rsum[rt << 1] + lsum[rt << 1 | 1] >= x) return m - rsum[rt << 1] + 1;
 78     else query(x, rson);
 79 }
 80 
 81 int main() {
 82     int n, m;
 83     cin >> n >> m;
 84     build(1, n, 1);
 85     while (m--) {
 86         int a, b, c;
 87         scanf("%d", &a);
 88         if (a == 1) {
 89             scanf("%d", &b);
 90             if (msum[1] < b) {
 91                 puts("0");
 92                 continue;
 93             }
 94             int ans = query(b, 1, n, 1);
 95             printf("%d
", ans);
 96             update(ans, ans + b - 1, 1, 1, n, 1);
 97         }
 98         else {
 99             scanf("%d%d",&b, &c);
100             update(b, b + c - 1, 0, 1, n, 1);
101         }
102     }
103     return 0;
104 }