hdu4614Vases and Flowers

http://acm.hdu.edu.cn/showproblem.php?pid=4614
线段树的各种操作写的有点乱求插入位置是以区间K值的方法求出的向下更新
  1 #include <iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 using namespace std;
  6 #define N 50010
  7 int s[N<<2],lz[N<<2];
  8 void build(int l,int r,int w)
  9 {
 10     s[w] = r-l+1;
 11     lz[w] = -1;
 12     if(l==r)
 13     {
 14         s[w] = 1;
 15         return ;
 16     }
 17     int m = (l+r)>>1;
 18     build(l,m,w<<1);
 19     build(m+1,r,w<<1|1);
 20 }
 21 void pushup(int w)
 22 {
 23     s[w] = s[w<<1]+s[w<<1|1];
 24 }
 25 void pushdown(int l,int r,int w)
 26 {
 27     int m = (l+r)/2;
 28     if(lz[w]!=-1)
 29     {
 30         lz[w<<1] = lz[w<<1|1] = lz[w];
 31         if(lz[w])
 32         {
 33             s[w<<1] = m-l+1;
 34             s[w<<1|1] = r-m;
 35         }
 36         else
 37         s[w<<1] = s[w<<1|1] = 0;
 38         lz[w] = -1;
 39     }
 40 }
 41 int query(int p,int l,int r,int w)
 42 {
 43     if(l==r)
 44     {
 45         return l;
 46     }
 47     pushdown(l,r,w);
 48     int m = (l+r)>>1;
 49     if(p<=s[w<<1])
 50     return query(p,l,m,w<<1);
 51     else
 52     return query(p-s[w<<1],m+1,r,w<<1|1);
 53 }
 54 void update(int d,int a,int b,int l,int r,int w)
 55 {
 56     if(a<=l&&b>=r)
 57     {
 58         if(d)
 59         s[w] = r-l+1;
 60         else
 61         s[w] = 0;
 62         lz[w] = d;
 63         return ;
 64     }
 65     pushdown(l,r,w);
 66     int m = (l+r)>>1;
 67     if(a<=m)
 68     update(d,a,b,l,m,w<<1);
 69     if(b>m)
 70     update(d,a,b,m+1,r,w<<1|1);
 71     pushup(w);
 72 }
 73 int add(int a,int b,int l,int r,int w)
 74 {
 75     if(a<=l&&b>=r)
 76     {
 77         return s[w];
 78     }
 79     pushdown(l,r,w);
 80     int m = (l+r)>>1,re=0;
 81     if(a<=m)
 82     re+=add(a,b,l,m,w<<1);
 83     if(b>m)
 84     re+=add(a,b,m+1,r,w<<1|1);
 85     return re;
 86 }
 87 int main()
 88 {
 89     int t,n,m,k;
 90     //freopen("1004.in","r",stdin);
 91     //freopen("aa.txt","w",stdout);
 92     cin>>t;
 93     while(t--)
 94     {
 95         scanf("%d%d",&n,&m);
 96         build(0,n-1,1);
 97         while(m--)
 98         {
 99             int a,b;
100             scanf("%d%d%d",&k,&a,&b);
101             if(k==1)
102             {
103                 int ss;
104                 if(a>0)
105                 ss = add(0,a-1,0,n-1,1);
106                 else ss=0;
107                 int x = query(ss+1,0,n-1,1);
108                 if(s[1]-ss<b)
109                 b = s[1]-ss;
110                 int y = query(ss+b,0,n-1,1);
111                 if(ss==s[1])
112                 printf("Can not put any one.
");
113                 else
114                 {printf("%d %d
",x,y);
115                 update(0,x,y,0,n-1,1);
116                 }
117             }
118             else
119             {
120                 int sx = add(a,b,0,n-1,1);
121                 //cout<<sx<<" ,"<<endl;
122 
123                 if(b>n-1)
124                 b = n-1;
125                 printf("%d
",b-a+1-sx);
126                 update(1,a,b,0,n-1,1);
127             }
128         }
129         puts("");
130     }
131     return 0;
132 }
View Code