本文共 6544 字,大约阅读时间需要 21 分钟。
Description
Input
Output
Sample Input
5 10P 1 2 3P 2 3 4Q 2 3Q 1 3P 3 5 4P 1 2 7Q 1 3Q 3 4P 5 5 8Q 1 50 0
Sample Output
43 44 744 7 8
代码://// main.cpp// 线段树区间合并//// Created by liuzhe on 16/11/11.// Copyright © 2016年 my_code. All rights reserved.//#include#include #include #include #include #include using namespace std;//hdu 5023 const int maxn=100000+10;int add[maxn<<2];int sum[maxn<<2];void pushup(int root){ sum[root]=sum[root<<1]+sum[root<<1|1];}void pushdown(int root,int m){ if(add[root]) { add[root<<1]=add[root]; add[root<<1|1]=add[root]; sum[root<<1]=add[root]; sum[root<<1|1]=add[root]; add[root]=0; //将标记向儿子移动后,父亲的延迟标记清除。传递后,当前节点标记域为空。 }}void build(int l,int r,int root){ add[root]=0;//初始化为所有节点都未标记 if(l==r) { sum[root]=2; return ; } int mid = (l+r)>>1; build(l,mid,root<<1); build(mid+1,r,root<<1|1); pushup(root);}void update(int L,int R,int c,int l,int r,int root){ if(L==l&&R==r) { add[root]=1<<(c-1); sum[root]=1<<(c-1); return ; } pushdown(root,r-l+1);//延迟标记向下传递 int mid = (l+r)>>1; if(L<=mid) update(L,R,c,l,mid,root<<1); if(R>mid) update(L,R,c,mid+1,r,root<<1|1); pushup(root);}int query(int L,int R,int l,int r,int root){ if(L==l&&R==r) return sum[root]; pushdown(root,r-l+1); //要取root子节点的值,也要先把root的延迟标记向下移动 int mid = (l+r)>>1; int ret = 0; if(L<=mid) ret |= query(L,R,l,mid,root<<1); if(R>mid) ret |= query(L,R,mid+1,r,root<<1|1); return ret;}int main(int argc, const char * argv[]) { // insert code here... int N,Q; int a,b,c; while(cin>>N>>Q) { if(!N&&!Q) break; getchar(); build(1,N,1); while(Q--) { char op; op=getchar(); if(op=='Q') { scanf("%d%d",&a,&b); //if(a>b) // swap(a,b); int tt=query(a,b,1,N,1); int flag=0; for(int i=1;i<=30;i++) { if(tt>>(i-1)&1 && !flag) { printf("%d",i); flag= 1; } else if(tt>>(i-1)&1 ) printf("%d",i); } printf("\n"); } else { scanf("%d%d%d",&a,&b,&c); update(a,b,c,1,N,1); } } } //std::cout << "Hello, World!\n"; return 0;}/*#define lson l , mid , rt << 1#define rson mid + 1 , r , rt << 1 | 1#define LL intconst int maxn = 1100017;LL add[maxn<<2];LL sum[maxn<<2];void PushUp(int rt){ //把当前结点的信息更新到父结点 sum[rt] = sum[rt<<1] | sum[rt<<1|1];//总共的颜色}void PushDown(int rt,int m){ if(add[rt]) { add[rt<<1] = add[rt]; add[rt<<1|1] = add[rt]; sum[rt<<1] = add[rt] ; sum[rt<<1|1] = add[rt] ; add[rt] = 0;//将标记向儿子节点移动后,父节点的延迟标记去掉 //传递后,当前节点标记域清空 }}void build(int l,int r,int rt){ add[rt] = 0;//初始化为所有结点未被标记 if (l == r) { sum[rt]=2;//初始颜色为2 return ; } int mid = (l + r) >> 1; build(lson); build(rson); PushUp(rt);}void update(int L,int R,int c,int l,int r,int rt){ if (L <= l && r <= R) { add[rt] =1<<(c-1);//位运算左移表示有某种颜色 sum[rt] =1<<(c-1); return ; } PushDown(rt , r - l + 1);//----延迟标志域向下传递 int mid = (l + r) >> 1; if (L <= mid) update(L , R , c , lson);//更新左儿子 if (mid < R) update(L , R , c , rson);//更新右儿子 PushUp(rt);}LL query(int L,int R,int l,int r,int rt){ if (L <= l && r <= R) { return sum[rt]; } //要取rt子节点的值时,也要先把rt的延迟标记向下移动 PushDown(rt , r - l + 1); int mid = (l + r) >> 1; LL ret = 0; if (L <= mid) ret |= query(L , R , lson); if (mid < R) ret |= query(L , R , rson); return ret;}int main(){ int N , Q; int a , b , c; while(scanf("%d%d",&N,&Q)) { if(N==0 && Q==0) break; build(1 , N , 1);//建树 while(Q--)//Q为询问次数 { char op[2]; scanf("%s",op); if(op[0] == 'Q')//Q为询问次数 { scanf("%d%d",&a,&b); LL tt=query(a , b , 1 , N , 1); LL flag = 0; for(int i=1; i<=30; i++) { if(tt>>(i-1)&1 && flag==0) { printf("%d",i); flag = 1; } else if(tt>>(i-1)&1) printf(" %d",i); } printf("\n"); } else { scanf("%d%d%d",&a,&b,&c); update(a , b , c , 1 , N , 1); } } } return 0;}*/
转载地址:http://bcali.baihongyu.com/