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
