题目原文废话太多太多太多，我就不copyandpaste到这里啦。。发个链接吧
题目
题目意思就是：P l r c 将区间 [l ，r]上的颜色变成c Q l r 就是打印出区间[l,r]中所有的颜色，并且要升序排列出来，注意最坑的就是各个区间的颜色初始化为2，这个条件竟然夹杂在那又长又臭的题目的某个角落里面！！
比赛的时候思路是有的，并且也能想到用set来撸，哎，对set的用法太挫逼了，写线段树又写得太挫逼了，后来补回这道题的时候，才发现其实是一道非常常规的线段树，所以最近给自己留了20道线段树慢慢刷，主要是能够更加熟练地写出线段树的模板，因为我发觉之前只是看得懂别人写的线段树的代码，却很少完全靠自己去敲出来，今天在补这道题的时候依然wa了很多次，最终才发现在query的那里忘记PushDown了 QAQ，废话少说 直接贴代码：
#include <cstdio>
#include <iostream>
#include <queue>
#include <set>
#include <cstring>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int maxn = ;
set<int> ans;
int SIZE;
int sum[maxn<<];
void PushDown(int rt){
if(sum[rt]){
sum[rt<<] = sum[rt];
sum[rt<<|] = sum[rt];
sum[rt] = ;
}
}
void build(int l,int r,int rt){
if(l == r){
sum[rt] = ;return;
}
int m = (l + r) >>;
build(lson);
build(rson);
return ;
}
void update(int L,int R,int c,int l,int r,int rt){
if(L <= l&&r <= R){
sum[rt] = c;
return ;
}
int m = (l + r)>>;
PushDown(rt);
if(L <= m) update(L,R,c,lson); if(m < R) update(L,R,c,rson);
return ;
}
void query(int L,int R,int l,int r,int rt){
//if(rt > SIZE) return;
if(L <= l&&r <= R&&sum[rt]){
ans.insert(sum[rt]);
return ;
}
PushDown(rt);
int m = (l + r)>>;
if(L <= m) query( L, R,lson);
if(m < R) query( L, R,rson);
return;
}
void print(){
set<int>::iterator it;
it = ans.begin();
cout<<*it;
ans.erase(it);
for(it = ans.begin();it != ans.end();++it)
printf(" %d",*it);
puts("");
}
void print_debug(){
cout<<"sum: "<<endl;
for(int i = ;i <= ;i++)
cout<<sum[i]<<" ";
puts("");
}
int main(){
int N,Q,a,b,c;
char ope[];
while(~scanf("%d%d",&N,&Q)&&(N+Q)){
SIZE = (N+)*N/;
memset(sum,,sizeof(sum));
build(,N,);
while(Q--){
scanf("%s",ope);
if(ope[] == 'Q'){
scanf("%d%d",&a,&b);
ans.clear();
query(a,b,,N,);
print();
}else{
scanf("%d%d%d",&a,&b,&c);
update(a,b,c,,N,);
//print_debug();
}
}
}
return ;
}
然后我又看到了另一份比较好玩的代码，是通过巧妙的位移运算来表示的，恩 感觉挺好的 链接请点击~
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; #define lson l , mid , rt << 1
#define rson mid + 1 , r , rt << 1 | 1
#define LL int const int maxn = ;
LL add[maxn<<];
LL sum[maxn<<];
void PushUp(int rt)
{
//把当前结点的信息更新到父结点
sum[rt] = sum[rt<<] | sum[rt<<|];//总共的颜色
}
void PushDown(int rt,int m)
{
if(add[rt])
{
add[rt<<] = add[rt];
add[rt<<|] = add[rt];
sum[rt<<] = add[rt] ;
sum[rt<<|] = add[rt] ;
add[rt] = ;//将标记向儿子节点移动后，父节点的延迟标记去掉
//传递后，当前节点标记域清空
}
}
void build(int l,int r,int rt)
{
add[rt] = ;//初始化为所有结点未被标记
if (l == r)
{
sum[rt]=;//初始颜色为2
return ;
}
int mid = (l + r) >> ;
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] =<<(c-);//位运算左移表示有某种颜色
sum[rt] =<<(c-);
return ;
}
PushDown(rt , r - l + );//----延迟标志域向下传递
int mid = (l + r) >> ;
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 + );
int mid = (l + r) >> ;
LL ret = ;
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== && Q==)
break;
build( , N , );//建树
while(Q--)//Q为询问次数
{
char op[];
scanf("%s",op);
if(op[] == 'Q')//Q为询问次数
{
scanf("%d%d",&a,&b);
LL tt=query(a , b , , N , );
LL flag = ;
for(int i=; i<=; i++)
{
if(tt>>(i-)& && flag==)
{
printf("%d",i);
flag = ;
}
else if(tt>>(i-)&)
printf(" %d",i);
}
printf("\n");
}
else
{
scanf("%d%d%d",&a,&b,&c);
update(a , b , c , , N , );
}
}
}
return ;
}