HDU 4614 Vases and Flowers

题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=4614

----------------------------------------------------------------------------------

较为麻烦的一道线段树题目为了更方便处理可以把

查询左端点查询右端点区间查询这三个查询分开写

最后复杂度是 $O(mlog(n))$的 $($下面的代码就是用的这个思路$)$

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cmath>
  4 #include <algorithm>
  5 using namespace std;
  6 const int N = 50010;
  7 int sum[N << 2], flag[N << 2];
  8 int t, n, m;
  9 void pushdown(int x, int tl, int tr)
 10 {
 11     if(!flag[x])
 12         return;
 13     flag[x << 1] = flag[x << 1 | 1] = flag[x];
 14     if(flag[x] & 1)
 15         sum[x << 1] = sum[x << 1 | 1] = 0;
 16     else
 17     {
 18         int mid = (tl + tr) >> 1;
 19         sum[x << 1] = mid - tl + 1;
 20         sum[x << 1 | 1] = tr - mid;
 21     }
 22     flag[x] = 0;
 23 }
 24 void update(int x, int L, int R, int tl, int tr, int y)
 25 {
 26     if(L <= tl && tr <= R)
 27     {
 28         flag[x] = y;
 29         if(y & 1)
 30             sum[x] = 0;
 31         else
 32             sum[x] = tr - tl + 1;
 33         return;
 34     }
 35     int mid = (tl + tr) >> 1;
 36     pushdown(x, tl, tr);
 37     if(L <= mid)
 38         update(x << 1, L, R, tl, mid, y);
 39     if(mid < R)
 40         update(x << 1 | 1, L, R, mid + 1, tr, y);
 41     sum[x] = sum[x << 1] + sum[x << 1 | 1];
 42 }
 43 int queryl(int x, int L, int tl, int tr)
 44 {
 45     if(!sum[x])
 46             return -1;
 47     if(tl == tr)
 48         return tl;
 49     int mid = (tl + tr) >> 1;
 50     pushdown(x, tl, tr);
 51     int re = -1;
 52     if(L <= mid && sum[x << 1])
 53         re = queryl(x << 1, L, tl, mid);
 54     if(re != -1)
 55         return re;
 56         return queryl(x << 1 | 1, L, mid + 1, tr);
 57 }
 58 int queryr(int x, int L, int tl, int tr, int &num)
 59 {
 60     if(tl == tr)
 61     {
 62         num -= sum[x];
 63         return tl;
 64     }
 65     int mid = (tl + tr) >> 1;
 66     pushdown(x, tl, tr);
 67     if(L <= tl)
 68     {
 69         if(sum[x << 1] >= num || !sum[x << 1 | 1])
 70             return queryr(x << 1, L, tl, mid, num);
 71         num -= sum[x << 1];
 72         return queryr(x << 1 | 1, L, mid + 1, tr, num);
 73     }
 74     if(L <= mid)
 75     {
 76         int re = queryr(x << 1, L, tl, mid, num);
 77         if(!num || !sum[x << 1 | 1])
 78             return re;
 79     }
 80     return queryr(x << 1 | 1, L, mid + 1, tr, num);
 81 }
 82 int query(int x, int L, int R, int tl, int tr)
 83 {
 84     if(L <= tl && tr <= R)
 85         return tr - tl + 1 - sum[x];
 86     int mid = (tl + tr) >> 1, re = 0;
 87     pushdown(x, tl, tr);
 88     if(L <= mid)
 89         re += query(x << 1, L, R, tl, mid);
 90     if(mid < R)
 91         re += query(x << 1 | 1, L, R, mid + 1, tr);
 92     return re;
 93 }
 94 int main()
 95 {
 96     scanf("%d", &t);
 97     while(t--)
 98     {
 99         scanf("%d%d", &n, &m);
100         memset(sum, 0, sizeof sum);
101         memset(flag, 0, sizeof flag);
102         update(1, 0, n - 1, 0, n - 1, 2);
103         int x, y, z;
104         while(m--)
105         {
106             scanf("%d%d%d", &x, &y, &z);
107             if(x == 1)
108             {
109                 int L = queryl(1, y, 0, n - 1);
110                 if(L == -1)
111                 {
112                     puts("Can not put any one.");
113                     continue;
114                 }    
115                 int R = queryr(1, L, 0, n - 1, z);
116                 printf("%d %d
", L, R);
117                 update(1, L, R, 0, n - 1, 1);
118             }
119             else
120             {
121                 printf("%d
", query(1, y, z, 0, n - 1));
122                 update(1, y, z, 0, n - 1, 2);
123             }
124         }
125         puts("");
126     }
127     return 0;
128 }

----------------------------------------------------------------------------------

不过如果不想写这么多判断的话也可以多写个二分这样就只要区间查询

然而复杂度就会变成$O(mlog^2(n))$