首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。