poj 2777(遅延更新＋線分樹)
4247 ワード
Count Color
Time Limit:1000 MS
メモリLimit:65536 K
Total Submissions:31475
Acceepted:9433
Description
Chosen Proble m Solving and Program design as,you are required to solive all kids of probles.Here,we get a new problem.
The e e is a very long board with length L centimeter、L is a positive integer、so we can evernly divide the board into L segments、and the y are labeled by 1、2、…L from left to Right、each is 1 centimewers.Nollaton.
1.「C A B C」Color the board from segment A to segment B withカラーカラーC.
2.「P A B」Output the number of different colors painted between segment A and segment B(including)
In our daily life、we have very few wods to describe a色(red、green、blue、yelloww...)、so you may asume that the total number of different colors T colorsT isssmake.Tomakeitsimple、we express thethethethethethethe aapapapapapapapapapapapapapapapapars the the thethethe thethethethe affs s s s s thethethethethethethethethethethersrsrs aaaaaffs s thethethethethethethethethethethethe aaafffs s s s thethethethethetheof problem is left to your.
Input
First line of input contains L(1<=L==100000)、T(1==T<=30)and O(1==O==100000).Here O denotes the number of operations.Follwing O lines,each contains"C"or"P B"(herstainger A,arefirs A,arever.)
Output
Ouut result of the output operation in order、each line contains a number.
Sample Input
POJ Monthly-20.03.26、dododo
この問題は与えられた区間の色の種類数を要求します.頻繁な更新と照会が必要なので、時間の複雑さを減らすには線分樹が必要です.また、区間で更新操作をするため、毎回リーフノードに更新すると、必ずタイムアウトします.私たちは線分樹の成段遅れの更新が必要です.
本題については、染める対象を点として見てもいいです.初期の時点では全ての点が色1です.
私たちは何かの点の色を1にする必要があります.これはちょっと面倒くさいです.ルートノードの色を1としてマークすることができます.
更新操作として、更新したい区間が[l,r]であれば、区間をいくつかの連続と区間を[l,r]の中間ノード区間に更新し、各中間点区間が純色であることを保証します.
具体的なやり方は、更新操作があるノードに来た時、
間隔を更新したいなら、ちょうどノードカバレッジ区間に等しいです.ノードの色を修正して終了します.あるノードカバレッジ区間を通過すると更新したい区間より大きい場合は、このノードの状態を左右のサブノードに押してから、この区間の色違いを修正し、カットは区間を更新して、左右のサブノード区間に更新を続けます.
クエリーとして動作する場合は、クエリ区間が［l,r］である場合、あるノードの色が純色であることを調べたら、この区間は一つの色しかないということです.純色でない場合、カットは照会区間から左右のサブノード区間まで検索操作を続けます.
具体的にコードを参照:
Time Limit:1000 MS
メモリLimit:65536 K
Total Submissions:31475
Acceepted:9433
Description
Chosen Proble m Solving and Program design as,you are required to solive all kids of probles.Here,we get a new problem.
The e e is a very long board with length L centimeter、L is a positive integer、so we can evernly divide the board into L segments、and the y are labeled by 1、2、…L from left to Right、each is 1 centimewers.Nollaton.
1.「C A B C」Color the board from segment A to segment B withカラーカラーC.
2.「P A B」Output the number of different colors painted between segment A and segment B(including)
In our daily life、we have very few wods to describe a色(red、green、blue、yelloww...)、so you may asume that the total number of different colors T colorsT isssmake.Tomakeitsimple、we express thethethethethethethe aapapapapapapapapapapapapapapapapars the the thethethe thethethethe affs s s s s thethethethethethethethethethethersrsrs aaaaaffs s thethethethethethethethethethethethe aaafffs s s s thethethethethetheof problem is left to your.
Input
First line of input contains L(1<=L==100000)、T(1==T<=30)and O(1==O==100000).Here O denotes the number of operations.Follwing O lines,each contains"C"or"P B"(herstainger A,arefirs A,arever.)
Output
Ouut result of the output operation in order、each line contains a number.
Sample Input
2 2 4
C 1 1 2
P 1 2
C 2 2 2
P 1 2
2
1
POJ Monthly-20.03.26、dododo
この問題は与えられた区間の色の種類数を要求します.頻繁な更新と照会が必要なので、時間の複雑さを減らすには線分樹が必要です.また、区間で更新操作をするため、毎回リーフノードに更新すると、必ずタイムアウトします.私たちは線分樹の成段遅れの更新が必要です.
本題については、染める対象を点として見てもいいです.初期の時点では全ての点が色1です.
私たちは何かの点の色を1にする必要があります.これはちょっと面倒くさいです.ルートノードの色を1としてマークすることができます.
更新操作として、更新したい区間が[l,r]であれば、区間をいくつかの連続と区間を[l,r]の中間ノード区間に更新し、各中間点区間が純色であることを保証します.
具体的なやり方は、更新操作があるノードに来た時、
間隔を更新したいなら、ちょうどノードカバレッジ区間に等しいです.ノードの色を修正して終了します.あるノードカバレッジ区間を通過すると更新したい区間より大きい場合は、このノードの状態を左右のサブノードに押してから、この区間の色違いを修正し、カットは区間を更新して、左右のサブノード区間に更新を続けます.
クエリーとして動作する場合は、クエリ区間が［l,r］である場合、あるノードの色が純色であることを調べたら、この区間は一つの色しかないということです.純色でない場合、カットは照会区間から左右のサブノード区間まで検索操作を続けます.
具体的にコードを参照:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN=100000+10;
int color[50];
struct node
{
int left,right,kind;
}tree[MAXN*4];
void build(int id,int left,int right)
{
tree[id].left=left;
tree[id].right=right;
tree[id].kind=1;
if(tree[id].left==tree[id].right)
return ;
int mid=(tree[id].left+tree[id].right)>>1;
build(id<<1,left,mid);
build((id<<1)|1,mid+1,right);
}
void updata(int id,int left,int right,int color)
{
if(tree[id].left==left&&tree[id].right==right||color==tree[id].kind)//color==tree[id].kind
{
tree[id].kind=color;
return ;
}
if(tree[id].kind!=0)
{
tree[id<<1].kind=tree[(id<<1)|1].kind=tree[id].kind;
tree[id].kind=0;//
}
int mid=(tree[id].left+tree[id].right)>>1;
if(right<=mid)updata(id<<1,left,right,color);
else if(left>mid)updata((id<<1)|1,left,right,color);
else
{
updata(id<<1,left,mid,color);
updata((id<<1)|1,mid+1,right,color);
}
}
void query(int id,int left,int right)
{
if(tree[id].kind>0)//
{
color[tree[id].kind]++;
return ;
}
int mid=(tree[id].left+tree[id].right)>>1;
if(right<=mid)query(id<<1,left,right);
else if(left>mid)query((id<<1)|1,left,right);
else
{
query(id<<1,left,mid);
query((id<<1)|1,mid+1,right);
}
}
int main()
{
int l,t,o,i,left,right,col,tmp,sum;
char cmd[5];
while(~scanf("%d%d%d",&l,&t,&o))
{
build(1,1,l);
while(o--)
{
scanf("%s",cmd);
if(cmd[0]=='P')
{
sum=0;
scanf("%d%d",&left,&right);
memset(color,0,sizeof(color));
query(1,left,right);
for(i=1;i<=t;i++)
{
if(color[i])
sum++;
}
printf("%d
",sum);
}
else
{
scanf("%d%d%d",&left,&right,&col);
updata(1,left,right,col);
}
}
}
return 0;
}