5 10 P 1 2 3 P 2 3 4 Q 2 3 Q 1 3 P 3 5 4 P 1 2 7 Q 1 3 Q 3 4 P 5 5 8 Q 1 5 0 0
4 3 4 4 7 4 4 7 8
//218ms
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <set>
using namespace std;
const int maxn=1000100;
set <int> s;
struct node
{
int lazy;
int left;
int right;
int value;
int mid()
{
return (left+right)>>1;
}
}tree[3*maxn];
int n;
void built(int n,int left,int right)
{
tree[n].lazy=0;
tree[n].left=left;
tree[n].right=right;
if(left==right)
{
tree[n].value=2;
return;
}
int mid=tree[n].mid();
built(n<<1,left,mid);
built(n<<1|1,mid+1,right);
tree[n].value=2;
}
void pushdown(int rt)
{
if(tree[rt].lazy)
{
tree[rt<<1].lazy=tree[rt<<1|1].lazy=tree[rt].lazy;
tree[rt<<1].value=tree[rt].value;
tree[rt<<1|1].value=tree[rt].value;
tree[rt].lazy=0;
}
}
void update(int rt,int L,int R,int val)
{
if(L<=tree[rt].left&&tree[rt].right<=R)
{
tree[rt].lazy=1;
tree[rt].value=val;
return ;
}
pushdown(rt);//向下更新一次
int mid=tree[rt].mid();
if(L<=mid)
update(rt<<1,L,R,val);
if(R>mid)
update(rt<<1|1,L,R,val);
if(tree[rt<<1].value==tree[rt<<1|1].value)
tree[rt].value=tree[rt<<1].value;
else
tree[rt].value=0;
}
void quarry(int rt,int left,int right)//查询
{
if(left>tree[rt].right||right<tree[rt].left)
{
return;
}
if(tree[rt].value)
{
s.insert(tree[rt].value);
return;
}
quarry(rt<<1,left,right);
quarry(rt<<1|1,left,right);
}
int main()
{
int m,x,y,z;
while(~scanf("%d%d",&n,&m)&&n+m)
{
built(1,1,n);
char c;
while(m--)
{
cin>>c;
if(c=='P')
{
scanf("%d%d%d",&x,&y,&z);
update(1,x,y,z);
}
else
{
scanf("%d%d",&x,&y);
s.clear();
quarry(1,x,y);
set<int>::iterator it;
for(it=s.begin();it!=s.end();it++)
{
if(it==s.begin())
printf("%d",*it);
else
printf(" %d",*it);
}
printf("\n");
}
}
}
return 0;
}
hdu 5023 A Corrupt Mayor's Performance Art(广州网络赛)
原文:http://blog.csdn.net/caduca/article/details/39449361