hdu 5023 A Corrupt Mayor's Performance Art(线段树区间更新)

#include
  
   
#include
   
     #include
    
      #include
     
       using namespace std; int tree[5001000],add[5001000]; int color[50]; int n,m; void pushup(int pos) { tree[pos]=tree[pos<<1]|tree[pos<<1|1]; //更新父节点 } void pushdown(int pos) { if(add[pos]) { add[pos<<1]=add[pos]; add[pos<<1|1]=add[pos]; tree[pos<<1]=add[pos]; tree[pos<<1|1]=add[pos]; add[pos]=0; //子节点更新后，父节点的延迟标记去掉 } } void build(int l,int r,int pos) { add[pos]=0; //初始时，所有节点都未标记 if(l==r) { tree[pos]=2; //初始时，颜色为2 return; } int mid=(l+r)/2; build(l,mid,2*pos); build(mid+1,r,2*pos+1); pushup(pos); } void update(int L,int R,int pos,int l,int r,int val) { if(l<=L&&r>=R) { tree[pos]=val; add[pos]=val; return; } pushdown(pos); //向下更新 int mid=(L+R)/2; if(l<=mid) update(L,mid,pos<<1,l,r,val); if(r>





mid) update(mid+1,R,pos<<1|1,l,r,val); pushup(pos); } int Query(int L,int R,int pos,int l,int r) { if(l<=L&&r>=R) return tree[pos]; pushdown(pos); int mid=(L+R)/2; if(l>mid) Query(mid+1,R,pos<<1|1,l,r); else if(r<=mid) Query(L,mid,pos<<1,l,r); else return Query(L,mid,pos<<1,l,r)|Query(mid+1,R,pos<<1|1,l,r); } int main() { int i,j,k,a,b,c; char ch[50]; while(scanf("%d%d",&n,&m)!=EOF) { if(n==0||m==0) break; build(1,n,1); for(j=0;j