首页 > 代码库 > hdu5023--A Corrupt Mayor's Performance Art

hdu5023--A Corrupt Mayor's Performance Art

来源:2014 ACM/ICPC Asia Regional Guangzhou Online

题意:长度为n的一个线段,1-30为颜色代号。初始状态每个单位长度颜色都为2,然后有q次操作,P操作把区间内的颜色全部换为别的颜色,Q操作从小到大输出区间内所有的颜色代号。

线段树区间更新(裸题),一场网络赛让我学会了区间更新。

#include <set>#include <map>#include <cmath>#include <ctime>#include <queue>#include <stack>#include <cctype>#include <cstdio>#include <string>#include <vector>#include <cstdlib>#include <cstring>#include <iostream>#include <algorithm>using namespace std;typedef unsigned long long ull;typedef long long ll;const int inf = 0x3f3f3f3f;const double eps = 1e-8;const int maxn = 1e6+10;int n,m,seg[maxn<<2];bool ans[35];void push_down(int l,int r,int pos){	if (~seg[pos])	{		seg[pos<<1] = seg[pos<<1|1] =seg[pos];	}	seg[pos] = -1;}void push_up(int l,int r,int pos){	if (seg[pos<<1] == seg[pos<<1|1])		seg[pos] = seg[pos<<1];	else		seg[pos] = -1;}void update(int l,int r,int pos,int ua,int ub,int col){	if (ua <= l && ub >= r)	{		seg[pos] = col;		return;	}	if (~seg[pos])		push_down(l,r,pos);	int mid = (l + r) >> 1;	if (ua <= mid)		update(l,mid,pos<<1,ua,ub,col);	if (ub > mid)		update(mid+1,r,pos<<1|1,ua,ub,col);	push_up(l,r,pos);}void query(int l,int r,int pos,int ua,int ub){	if (~seg[pos])	{		ans[seg[pos]] = 1;		return;	}	int mid = (l + r) >> 1;	if (ua <= mid)		query(l,mid,pos<<1,ua,ub);	if (ub > mid)		query(mid+1,r,pos<<1|1,ua,ub);}int main(void){    #ifndef ONLINE_JUDGE        freopen ("in.txt","r",stdin);    #endif    while (scanf ("%d%d",&n,&m),n&&m)	{		update(1,n,1,1,n,2);		for (int i = 0; i < m; i++)		{			char cmd[5];			scanf ("%s",cmd);			if (cmd[0] == ‘P‘)			{				int x,y,z;				scanf ("%d%d%d",&x,&y,&z);				update(1,n,1,x,y,z);			}			if (cmd[0] == ‘Q‘)			{				int x,y;				scanf ("%d%d",&x,&y);				memset(ans,0,sizeof(ans));				query(1,n,1,x,y);				bool first = 0;				for (int i = 1; i <= 30; i++)				{					if (ans[i])					{						if (!first)							printf("%d",i),first = 1;						else							printf(" %d",i);					}				}				printf("\n");			}		}	}    return 0;}

  

 

hdu5023--A Corrupt Mayor's Performance Art