hdu 2871 Memory Control

这是一道模拟内存分配操作的题目，几乎包含了线段树的各种基本操作，跟poj3667 hotel差不多的功能，只是多了一个统计区间个数的操作。
由于这题是断断续续打上去的，花的时间也比较长。可能有些代码写的不太好。
View Code
  1 #include <stdio.h>
  2 #define lson l,m,rt<<1
  3 #define rson m+1,r,rt<<1|1
  4 #define maxn 50005
  5 struct node
  6 {
  7     int llen,rlen,maxlen,lnum,rnum,num,cnt;
  8 }setree[maxn<<2];
  9 struct 
 10 {
 11     int l,r,c;
 12 }idnum[maxn];
 13 int top,cnt;
 14 int max(int a,int b)
 15 {
 16     return a>b?a:b;
 17 }
 18 void build(int l,int r,int rt)
 19 {
 20     setree[rt].llen=setree[rt].rlen=setree[rt].maxlen=r-l+1;
 21     setree[rt].num=setree[rt].lnum=setree[rt].rnum=-1;
 22     setree[rt].cnt=0;
 23     if(l==r)
 24     return ;
 25     int m=(l+r)>>1;
 26     build(lson);
 27     build(rson);
 28 }
 29 void pushup(int rt,int len)
 30 {
 31     setree[rt].llen=setree[rt<<1].llen;
 32     setree[rt].lnum=setree[rt<<1].lnum;
 33     if(setree[rt<<1].llen==len-len/2)
 34     setree[rt].llen+=setree[rt<<1|1].llen;
 35     
 36     setree[rt].rlen=setree[rt<<1|1].rlen;
 37     setree[rt].rnum=setree[rt<<1|1].rnum;
 38     if(setree[rt<<1|1].rlen==len/2)
 39     setree[rt].rlen+=setree[rt<<1].rlen;
 40     
 41     setree[rt].maxlen=max(setree[rt<<1].maxlen,setree[rt<<1|1].maxlen);
 42     setree[rt].maxlen=max(setree[rt].maxlen,setree[rt<<1].rlen+setree[rt<<1|1].llen);
 43     
 44     setree[rt].cnt=setree[rt<<1].cnt+setree[rt<<1|1].cnt;
 45     if(setree[rt<<1].rnum==setree[rt<<1|1].lnum&&setree[rt<<1].rnum>0)
 46     setree[rt].cnt--;
 47 }
 48 void pushdown(int rt,int len)
 49 {
 50     if(setree[rt].num!=-1){
 51         setree[rt<<1].llen=setree[rt<<1].rlen=setree[rt<<1].maxlen=setree[rt].num?0:len-len/2;
 52         setree[rt<<1|1].llen=setree[rt<<1|1].rlen=setree[rt<<1|1].maxlen=setree[rt].num?0:len/2;
 53         setree[rt<<1].lnum=setree[rt<<1].rnum=setree[rt<<1].num=setree[rt].num;
 54         setree[rt<<1|1].lnum=setree[rt<<1|1].rnum=setree[rt<<1|1].num=setree[rt].num;
 55         setree[rt<<1].cnt=setree[rt<<1|1].cnt=setree[rt].num?1:0;
 56         setree[rt].num=-1;
 57     }
 58 }
 59 void update(int l,int r,int rt,int L,int R,int op)
 60 {
 61     if(L<=l&&r<=R){
 62         setree[rt].llen=setree[rt].rlen=setree[rt].maxlen=op?0:r-l+1;
 63         setree[rt].num=setree[rt].lnum=setree[rt].rnum=op;
 64         setree[rt].cnt=op?1:0;
 65         return ;
 66     }
 67     pushdown(rt,r-l+1);
 68     int m=(l+r)>>1;
 69     if(L<=m)
 70     update(lson,L,R,op);
 71     if(R>m)
 72     update(rson,L,R,op);
 73     pushup(rt,r-l+1);
 74 }
 75 int query(int l,int r,int rt,int num)
 76 {
 77     if(l==r)
 78     return l;
 79     pushdown(rt,r-l+1);
 80     int m=(l+r)>>1;
 81     if(setree[rt<<1].maxlen>=num)
 82     return query(lson,num);
 83     else if(setree[rt<<1].rlen+setree[rt<<1|1].llen>=num)
 84     return m-setree[rt<<1].rlen+1;
 85     else
 86     return query(rson,num);
 87 }
 88 int query1(int l,int r,int rt,int num)
 89 {
 90     if(l==r)
 91     return setree[rt].num;
 92     pushdown(rt,r-l+1);
 93     int m=(l+r)>>1;
 94     if(num<=m)
 95     return query1(lson,num);
 96     else
 97     return query1(rson,num);
 98 }
 99 int query2(int l,int r,int rt,int num)
100 {
101     if(l==r)
102     return l;
103     pushdown(rt,r-l+1);
104     int m=(l+r)>>1;    
105     if(setree[rt<<1].cnt>=num)
106     return query2(lson,num);
107     else{
108         num-=setree[rt<<1].cnt;
109         if(setree[rt<<1].cnt+setree[rt<<1|1].cnt>setree[rt].cnt)
110         num++;
111         return query2(rson,num);
112     }
113 }
114 int main()
115 {
116     int n,m,i;
117     while(~scanf("%d%d",&n,&m)){
118         build(1,n,1);
119         top=1;
120         while(m--){
121             char opp[5];
122             int a;
123             scanf("%s",opp);
124             if(opp[0]=='N'){
125                 scanf("%d",&a);
126                 if(a>setree[1].maxlen){
127                     printf("Reject New\n");
128                     continue;
129                 }
130                 int start=query(1,n,1,a);
131                 printf("New at %d\n",start);
132                 update(1,n,1,start,start+a-1,top);
133                 idnum[top].l=start;
134                 idnum[top].r=start+a-1;
135                 idnum[top].c=1;
136                 top++;
137             }
138             else if(opp[0]=='R'){
139                 top=1;
140                 printf("Reset Now\n");
141                 update(1,n,1,1,n,0);
142             }
143             else if(opp[0]=='F'){
144                 scanf("%d",&a);
145                 int ans=query1(1,n,1,a);
146                 if(ans==0||ans==-1){
147                     printf("Reject Free\n");
148                     continue;
149                 }
150                 printf("Free from %d to %d\n",idnum[ans].l,idnum[ans].r);
151                 update(1,n,1,idnum[ans].l,idnum[ans].r,0);
152                 idnum[ans].c=0;
153             }
154             else{
155                 scanf("%d",&a);
156                 if(a>setree[1].cnt){
157                     printf("Reject Get\n");
158                     continue;
159                 }
160                 int ans=query2(1,n,1,a);
161                 printf("Get at %d\n",ans);
162             }
163         }
164         printf("\n");
165     }
166     return 0;
167 }