hdu 2871 Memory Control(线段树)

重新认识vector - -其实就是链表式数组，或者说数组式链表？ 哈哈哈

其实还是跟 Hotel 一样，然后加了Get操作吧。

用vector维护一下有多少个区间嘛。

也学会了vector 的erase和insert的应用。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #define lson num<<1,s,mid #define rson num<<1|1,mid+1,e #define maxn 50005 using namespace std; int cov[maxn<<2]; int rmax[maxn<<2]; int lmax[maxn<<2]; int cmax[maxn<<2]; struct node { int st,ed; }; vector
        
         cq; void pushup(int num,int s,int e) { int mid=(s+e)>>1; cmax[num]=max(rmax[num<<1]+lmax[num<<1|1],max(cmax[num<<1],cmax[num<<1|1])); lmax[num]=lmax[num<<1]; rmax[num]=rmax[num<<1|1]; if(lmax[num]==mid-s+1)lmax[num]+=lmax[num<<1|1]; if(rmax[num]==e-mid)rmax[num]+=rmax[num<<1]; } void pushdown(int num,int s,int e) { if(cov[num]!=-1) { int mid=(s+e)>>1; cov[num<<1]=cov[num<<1|1]=cov[num]; cmax[num<<1]=lmax[num<<1]=rmax[num<<1]=cov[num] 0:mid-s+1; cmax[num<<1|1]=lmax[num<<1|1]=rmax[num<<1|1]=cov[num] 0:e-mid; cov[num]=-1; } } void build(int num,int s,int e) { cov[num]=-1; if(s==e) { lmax[num]=rmax[num]=cmax[num]=1; return; } int mid=(s+e)>>1; build(lson); build(rson); pushup(num,s,e); } void update(int num,int s,int e,int l,int r,int val) { if(l<=s && r>=e) { cov[num]=val; lmax[num]=rmax[num]=cmax[num]=val 0:e-s+1; return; } pushdown(num,s,e); int mid=(s+e)>>1; if(l<=mid)update(lson,l,r,val); if(r>mid)update(rson,l,r,val); pushup(num,s,e); } int query(int num,int s,int e,int val) { if(s==e) { return s; } pushdown(num,s,e); int mid=(s+e)>>1; if(cmax[num<<1]>=val)return query(lson,val); else if(rmax[num<<1]+lmax[num<<1|1]>=val)return mid+1-rmax[num<<1]; else return query(rson,val); } int bin(int key) { int l=0,r=cq.size()-1; while(l<=r) { int mid=(l+r)>>1; if(cq[mid].st<=key)l=mid+1; else r=mid-1; } return l-1; } int main() { int n,m; while(scanf("%d%d",&n,&m)!=EOF) { cq.clear(); build(1,1,n); while(m--) { char str[10]; scanf("%s",str); if(str[0]=='R') { cq.clear(); update(1,1,n,1,n,0); printf("Reset Now\n"); } else if(str[0]=='N') { int v; scanf("%d",&v); if(cmax[1]