题意：n个空房间。两种操作：1.选择最小的连续D个房间入住，并输出这连续D个房间的最小标号。2.将某个区间内的房间全部退房。
1 #include <cstdio> 2 #include <iostream> 3 #include <algorithm> 4 #define ll long long 5 #define lson l, m, rt<<1 6 #define rson m+1, r, rt<<1|1 7 #define st first 8 #define nd second 9 #define mp make_pair 10 #define pii pair<int, int> 11 #define gg puts("gg"); 12 using namespace std; 13 void gmax(int& a, int b){ 14 if(a < b) a = b; 15 } 16 const int N = 5e4+10; 17 struct Node{ 18 int lsum, rsum, sum; 19 int tag; 20 }; 21 Node T[N<<2]; 22 void pushup(int l, int r, int rt){ 23 T[rt].lsum = T[rt<<1].lsum, T[rt].rsum = T[rt<<1|1].rsum; 24 int m = l+r >> 1; 25 if(T[rt<<1].lsum == m-l+1) T[rt].lsum += T[rt<<1|1].lsum; 26 if(T[rt<<1|1].rsum == r-m) T[rt].rsum += T[rt<<1].rsum; 27 T[rt].sum = max(T[rt<<1].sum, T[rt<<1|1].sum); 28 gmax(T[rt].sum, T[rt<<1].rsum+T[rt<<1|1].lsum); 29 } 30 void pushdown(int l, int r, int rt){ 31 if(T[rt].tag != -1){ 32 T[rt<<1].tag = T[rt<<1|1].tag = T[rt].tag; 33 int m = l+r >> 1; 34 T[rt<<1].lsum = T[rt<<1].rsum = T[rt<<1].sum = T[rt].tag? m-l+1 : 0; 35 T[rt<<1|1].lsum = T[rt<<1|1].rsum = T[rt<<1|1].sum = T[rt].tag? r-m : 0; 36 T[rt].tag = -1; 37 } 38 } 39 void build(int l, int r, int rt){ 40 T[rt].lsum = T[rt].rsum = T[rt].sum = r-l+1; 41 T[rt].tag = -1; 42 if(l == r) 43 return ; 44 int m = l+r >> 1; 45 build(lson); 46 build(rson); 47 } 48 int query(int c, int l, int r, int rt){ 49 //printf("query %d: l %d, r %d, lson %d, rson %d, sum %d ", rt, l, r, T[rt].lsum, T[rt].rsum, T[rt].sum); 50 if(l == r) 51 return l; 52 pushdown(l, r, rt); 53 int m = l+r >> 1; 54 if(T[rt<<1].sum >= c) return query(c, lson); 55 if(T[rt<<1].rsum+T[rt<<1|1].lsum >= c) return m-T[rt<<1].rsum+1; 56 return query(c, rson); 57 } 58 void update(int L, int R, int c, int l, int r, int rt){ 59 if(L <= l&&r <= R){ 60 T[rt].tag = c; 61 T[rt].lsum = T[rt].rsum = T[rt].sum = c? r-l+1:0; 62 return ; 63 } 64 pushdown(l, r, rt); 65 int m = l+r >> 1; 66 if(L <= m) update(L, R, c, lson); 67 if(R > m) update(L, R, c, rson); 68 pushup(l, r, rt); 69 //printf("updaet %d: l %d, r %d, lson %d, rson %d, sum %d ", rt, l, r, T[rt].lsum, T[rt].rsum, T[rt].sum); 70 } 71 72 int main(){ 73 int n, m, x, y, op; 74 scanf("%d%d", &n, &m); 75 build(1, n, 1); 76 while(m--){ 77 scanf("%d", &op); 78 if(op == 1){ 79 scanf("%d", &x); 80 if(T[1].sum < x) puts("0"); 81 else { 82 int ret = query(x, 1, n, 1); 83 printf("%d ", ret); 84 update(ret, ret+x-1, 0, 1, n, 1); 85 } 86 } 87 else { 88 scanf("%d%d", &x, &y); 89 update(x, x+y-1, 1, 1, n, 1); 90 } 91 } 92 return 0; 93 }
后记：这也是线段树一经典题。不难。
主要是通过这种写法可以O(logn)的时间内完成离散化查询。不过平时一般都是二分+树状数组O(lognlogn)完成离散化查询。