【BZOJ 1018】[SHOI 2008]渋滞する交通traffic
1018:[SHOI 2008]渋滞する交通traffic
Time Limit: 3 Sec
Memory Limit: 162 MB
Submit: 1811
Solved: 580
[ Submit][ Status]
Description
ある日、ある種の通り抜け現象の作用で、あなたは伝説の小人国に来ました.小人国のレイアウトは非常に奇抜で、国全体の交通システムは2行C列の矩形のグリッドと見なすことができて、グリッドの上の各点は1つの都市を代表して、隣接する都市の間に1本の道があるので、全部で2 Cの都市と3 C-2本の道があります.小人国の交通状況は非常に悪い.交通渋滞のため、2つの都市の間の道路がつながっていない場合があり、渋滞が解決するまで、道路がスムーズになります.初めて来たあなたは交通部のある仕事を自薦することを決意しました.部長はあなたが科学技術が高度に発達した世界から来たと聞いて、病気になった小人国の交通システムを救うために、地方からクエリー応答システムを書くように要求したことを喜んでいます.小人国の交通部はあなたにいくつかの交通情報を提供して、あなたの任務は現在の交通状況に基づいて照会の質問に答えることです.交通情報は以下のいくつかのフォーマットに分けることができる:Close r 1 c 1 r 2 c 2:隣接する2つの都市(r 1,c 1)と(r 2,c 2)の間の道路が塞がれている;Open r 1 c 1 r 2 c 2:隣接する2つの都市(r 1,c 1)と(r 2,c 2)の間の道路が疎通された.Ask r 1 c 1 r 2 c 2:都市(r 1,c 1)と(r 2,c 2)が連通しているかどうかを尋ねる.この2つの都市が連通する経路がある場合、Yを返し、そうでなければNを返す.
Input
最初の行には、グリッドの列数を表す整数Cが1つしかありません.次のいくつかの行は、各行に1つの交通情報があり、個別の行「Exit」で終了します.最初はすべての道が渋滞していたと仮定します.30%のテストデータに対して、私たちはCが1000以下で、情報の条数が1000以下であることを保証します.100%のテストデータに対して、Cが100000以下、情報バー数が100000以下であることを保証します.
Output
クエリーごとに、YまたはNが出力されます.
Sample Input
2 Open 1 1 1 2 Open 1 2 2 2 Ask 1 1 2 2 Ask 2 1 2 2 Exit
Sample Output
Y N
線分樹で連通性を維持し、分類討論能力を試す私たちの問題!
区間l-rの場合、セグメントツリーは左上左下右上右下の4つの場所の連通性を維持します.私のプログラムでは:
(1,1) (1,2)
(2,1) (2,2)
h1:(1,1)-->(1,2)
h2:(2,1)-->(2,2)
s1:(1,1)-->(2,1)
s2:(1,2)-->(2,2)
x1:(1,1)-->(2,2)
x2:(1,2)-->(2,1)
この6つの情報を維持するとともに、区間を統合するため、1つのl[x][y][k]で(x,y)という位置と周囲との連通状況(うちk=1,2,3,4はそれぞれ上下左右との連通状況)を表す.
最初は合併を考えていたとき、ルートが非常に多かったような気がします.実際には、次の点に注意してください.
合併する2つの区間はすでにつながっていて、現在の区間の合併は2つの区間の境界を使うことを考慮すればいいです!
(具体的にはコードUpdateを参照)
最後に、l-rの接続状況をクエリーします.
l−rから直接行くか、lから前へrへ、rから後ろへlへ.
従って、1−l,l−r,r−nの3区間の連通を前処理し、それぞれa 1,a 2,a 3と記す.
もしa 1.s 2が連通と、a 2となる.s 1連通;a3.s 1が連通するとa 2になる.s 2連通.
そして縦座標によって検討すればいいのです(必ず周到に考えましょう!!).
悟り:
1.困難AC歴:
ツリーを構築する際にl=rのノードに対してh 1とh 2は1を与える.
Mergeの場合、必ずこのノードのlrに値を付けなければなりません.そうしないとREになります.
検索するときは区間ごとに2つの線分ツリー上の区間に分けられると思います..明らかに違います.の
検索時にx 1=x 2の場合、a 1とa 3がa 2のs 1とs 2を変える可能性があるため、議論のルートが必要!!!
2.線分樹が連通性を維持できることを初めて知り、不思議な感じでした~
Time Limit: 3 Sec
Memory Limit: 162 MB
Submit: 1811
Solved: 580
[ Submit][ Status]
Description
ある日、ある種の通り抜け現象の作用で、あなたは伝説の小人国に来ました.小人国のレイアウトは非常に奇抜で、国全体の交通システムは2行C列の矩形のグリッドと見なすことができて、グリッドの上の各点は1つの都市を代表して、隣接する都市の間に1本の道があるので、全部で2 Cの都市と3 C-2本の道があります.小人国の交通状況は非常に悪い.交通渋滞のため、2つの都市の間の道路がつながっていない場合があり、渋滞が解決するまで、道路がスムーズになります.初めて来たあなたは交通部のある仕事を自薦することを決意しました.部長はあなたが科学技術が高度に発達した世界から来たと聞いて、病気になった小人国の交通システムを救うために、地方からクエリー応答システムを書くように要求したことを喜んでいます.小人国の交通部はあなたにいくつかの交通情報を提供して、あなたの任務は現在の交通状況に基づいて照会の質問に答えることです.交通情報は以下のいくつかのフォーマットに分けることができる:Close r 1 c 1 r 2 c 2:隣接する2つの都市(r 1,c 1)と(r 2,c 2)の間の道路が塞がれている;Open r 1 c 1 r 2 c 2:隣接する2つの都市(r 1,c 1)と(r 2,c 2)の間の道路が疎通された.Ask r 1 c 1 r 2 c 2:都市(r 1,c 1)と(r 2,c 2)が連通しているかどうかを尋ねる.この2つの都市が連通する経路がある場合、Yを返し、そうでなければNを返す.
Input
最初の行には、グリッドの列数を表す整数Cが1つしかありません.次のいくつかの行は、各行に1つの交通情報があり、個別の行「Exit」で終了します.最初はすべての道が渋滞していたと仮定します.30%のテストデータに対して、私たちはCが1000以下で、情報の条数が1000以下であることを保証します.100%のテストデータに対して、Cが100000以下、情報バー数が100000以下であることを保証します.
Output
クエリーごとに、YまたはNが出力されます.
Sample Input
2 Open 1 1 1 2 Open 1 2 2 2 Ask 1 1 2 2 Ask 2 1 2 2 Exit
Sample Output
Y N
線分樹で連通性を維持し、分類討論能力を試す私たちの問題!
区間l-rの場合、セグメントツリーは左上左下右上右下の4つの場所の連通性を維持します.私のプログラムでは:
(1,1) (1,2)
(2,1) (2,2)
h1:(1,1)-->(1,2)
h2:(2,1)-->(2,2)
s1:(1,1)-->(2,1)
s2:(1,2)-->(2,2)
x1:(1,1)-->(2,2)
x2:(1,2)-->(2,1)
この6つの情報を維持するとともに、区間を統合するため、1つのl[x][y][k]で(x,y)という位置と周囲との連通状況(うちk=1,2,3,4はそれぞれ上下左右との連通状況)を表す.
最初は合併を考えていたとき、ルートが非常に多かったような気がします.実際には、次の点に注意してください.
合併する2つの区間はすでにつながっていて、現在の区間の合併は2つの区間の境界を使うことを考慮すればいいです!
(具体的にはコードUpdateを参照)
最後に、l-rの接続状況をクエリーします.
l−rから直接行くか、lから前へrへ、rから後ろへlへ.
従って、1−l,l−r,r−nの3区間の連通を前処理し、それぞれa 1,a 2,a 3と記す.
もしa 1.s 2が連通と、a 2となる.s 1連通;a3.s 1が連通するとa 2になる.s 2連通.
そして縦座標によって検討すればいいのです(必ず周到に考えましょう!!).
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
using namespace std;
struct Node
{
int l,r,h1,h2,s1,s2,x1,x2;
}a[500005];
int n,l[3][100005][5];
void Build(int x,int l,int r)
{
a[x].l=l,a[x].r=r;
a[x].h1=a[x].h2=a[x].s1=a[x].s2=a[x].x1=a[x].x2=0;
if (l==r)
{
a[x].h1=a[x].h2=1;
return;
}
int m=(l+r)>>1;
Build(x<<1,l,m);
Build((x<<1)+1,m+1,r);
}
void Modi(int x1,int y1,int x2,int y2,int k)
{
if (x1==x2)
{
if (y1>y2) swap(y1,y2);
l[x1][y1][4]=l[x2][y2][3]=k;
}
else
{
if (x1>x2) swap(x1,x2);
l[x1][y1][2]=l[x2][y2][1]=k;
}
}
void Modis(int x)
{
a[x].s1=l[1][a[x].l][2];
a[x].s2=l[1][a[x].r][2];
a[x].x1=a[x].x2=0;
if (a[x].s1|a[x].s2)
a[x].x1=a[x].x2=1;
}
Node Merge(Node x,Node y)
{
if (x.l==y.l&&x.r==y.r) return x;
Node k;
int p1=l[1][x.r][4],p2=l[2][x.r][4];
k.h1=(x.h1&p1&y.h1)|(x.x1&p2&y.x2);
k.h2=(x.h2&p2&y.h2)|(x.x2&p1&y.x1);
k.s1=x.s1|(x.h1&p1&y.s1&p2&x.h2);
k.s2=y.s2|(y.h1&p1&x.s2&p2&y.h2);
k.x1=(x.h1&p1&y.x1)|(x.x1&p2&y.h2);
k.x2=(y.x2&p2&x.h2)|(y.h1&p1&x.x2);
k.l=x.l,k.r=y.r;
return k;
}
void Update1(int x,int l,int r)
{
int m=(a[x].l+a[x].r)>>1;
if (l==m)
{
a[x]=Merge(a[x<<1],a[(x<<1)+1]);
return;
}
if (l<m) Update1(x<<1,l,r);
else Update1((x<<1)+1,l,r);
a[x]=Merge(a[x<<1],a[(x<<1)+1]);
}
void Update2(int x,int k)
{
if (a[x].l==a[x].r&&a[x].l==k)
{
Modis(x);
return;
}
int m=(a[x].l+a[x].r)>>1;
if (k<=m) Update2(x<<1,k);
else Update2((x<<1)+1,k);
a[x]=Merge(a[x<<1],a[(x<<1)+1]);
}
Node Find(int x,int l,int r)
{
if (a[x].l>=l&&a[x].r<=r)
return a[x];
int m=(a[x].l+a[x].r)>>1;
if (r<=m) return Find(x<<1,l,r);
if (l>m) return Find((x<<1)+1,l,r);
return Merge(Find(x<<1,l,r),Find((x<<1)+1,l,r));
}
bool Query(int x1,int y1,int x2,int y2)
{
Node a1=Find(1,1,y1),a2=Find(1,y1,y2),a3=Find(1,y2,n);
a2.s1^=a1.s2,a2.s2^=a3.s1;
if (x1==x2)
{
if (x1==1) return a2.h1|(a2.s1&a2.h2&a2.s2)|(a2.s1&a2.x2)|(a2.x1&a2.s2);
else return a2.h2|(a2.s1&a2.h1&a2.s2)|(a2.s1&a2.x1)|(a2.s2&a2.x2);
}
if (x1<x2) return a2.x1|(a2.s1&a2.h2)|(a2.h1&a2.s2);
return a2.x2|(a2.s1&a2.h1)|(a2.h2&a2.s2);
}
int main()
{
scanf("%d",&n);
Build(1,1,n);
char s[10];
while (scanf("%s",s)!=EOF)
{
if (s[0]=='E') break;
int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
switch(s[0])
{
case 'O':
Modi(x1,y1,x2,y2,1);
if (x1==x2)
Update1(1,min(y1,y2),max(y1,y2));
else
Update2(1,y1);
break;
case 'C':
Modi(x1,y1,x2,y2,0);
if (x1==x2)
Update1(1,min(y1,y2),max(y1,y2));
else
Update2(1,y1);
break;
case 'A':
if (y1>y2) swap(x1,x2),swap(y1,y2);
if (Query(x1,y1,x2,y2)) printf("Y
");
else printf("N
");
break;
}
}
return 0;
}
悟り:
1.困難AC歴:
ツリーを構築する際にl=rのノードに対してh 1とh 2は1を与える.
Mergeの場合、必ずこのノードのlrに値を付けなければなりません.そうしないとREになります.
検索するときは区間ごとに2つの線分ツリー上の区間に分けられると思います..明らかに違います.の
検索時にx 1=x 2の場合、a 1とa 3がa 2のs 1とs 2を変える可能性があるため、議論のルートが必要!!!
2.線分樹が連通性を維持できることを初めて知り、不思議な感じでした~