NOIP 2016毎日走るのが好き(線分樹/桶)
25706 ワード
タイトルの説明
cさんはランニングがとても面白いと思って、「毎日走るのが好き」というゲームを作ることにしました.毎日走るのが好きなのは1つの育成类のゲームで、プレーヤーが毎日时间通りにオンラインになって、カードを打つ任务を完成する必要があります.
このゲームの地図は,N個のノードとN−1個のエッジを含むツリーと見なすことができ,各エッジが2個のノードを接続し,任意の2つのノードが1つの経路で互いに達することができる.ツリー上のノード番号は、1からNまでの連続正の整数です.
今はプレイヤーがいて、最初のプレイヤーの起点はSiで、終点はTiです.毎日カードを打つ任務が始まる時、すべてのプレーヤーは0秒目に同時に自分の起点から出発して、毎秒1本の辺の速度を走って、間断なく最短の経路に沿って自分の終点に向かって走って、終点に着いた後にそのプレーヤーはカードを打つ任務を完成しました.(地図は木なので、一人一人の経路は唯一です)
Cちゃんはゲームの活躍度が知りたくて、ノードごとにオブザーバーが置かれていました.ノードのオブザーバーは、Wj秒目にプレイヤーを観察することを選択し、1人のプレイヤーがこのオブザーバーに観察され、そのプレイヤーがWj秒目にちょうどノードJに到着したときにのみ観察することができる.Cさんはオブザーバー一人一人が何人観察するか知りたいです.
注意:あるプレイヤーが自分のゴールに着いたら、そのプレイヤーはゲームを終了すると思います.彼はしばらく待ってからオブザーバーに観察されることはできません.すなわち、ノードJを終点とするプレイヤーに対して、Wj秒目に再び終点に到達すると、ノードJのオブザーバーはそのプレイヤーを観察できない.もし彼がちょうどWj秒でゴールに着いたら、ノードのオブザーバーはこのプレイヤーを観察することができます.
入力フォーマット
1行目には2つの整数NとMがある.このうちNはツリーのノード数を表し,またオブザーバーの数を表し,Mはプレイヤーの数を表す.
次に、n−1行の2つの整数UおよびVは、ノードUからノードVまでのエッジがあることを示す.
次の行のN個の整数で、そのうちの第1の整数はWjであり、ノードがオブザーバーに現れる時間を表す.
次にM行、1行あたり2つの整数SiとTiは、1人のプレイヤーの始点と終点を表す.
すべてのデータに対して、保証します.1<=Si,Ti<=N,0<=Wj<=N
出力フォーマット
1行N個の整数を出力し,j番目の整数はノードjのオブザーバーがどれだけの人を観察できるかを示す.
問題解決の考え方:
方法一:線分ツリー+ツリーチェーン分割
まず、どのようなプレイヤーが見られるかを考えてみましょう.それは、いつプレイヤーがノードに着くかということです.
プレイヤーの初期時の位置深さをdとする.
多分、プレイヤーが上に向かって歩いていると、0時に経路上のd深さの点、1時にd-1深さの点、2時にd-2まで歩いて深さの点になります.
では、上へ行く過程で、通過点のオブザーバーは等式(w+deep)=dを成立させるだけで、プレイヤーが見えます.
同じようにプレイヤーが下を向いているときにも似たような結論があります.プレイヤーの(d-2*パス上のlcaのdeep)=(w-deep)だけで見えます.
では、線分の木を開けて保存すればいいです.
各深さの2本の線分ツリーについて、下へ行くノードと上へ行くノードの観察値、すなわち、各プレイヤーのd上の線分ツリーは、各プレイヤーが経験した点に対して+1統一される.
つまり、ツリーチェーンに+1を付けると、単一のクエリーで済むようになります.
木の鎖の上に+1、木の鎖を使って分割すればいいです^^;
線分の木は大きな空間を占めてダイナミックに開くといいです
また、浅い深さの点では、最終的な下向きのインデックスが負になる可能性があることがわかりました.そのため、下向きのセグメントツリーインデックスには3 e 5が統一されています.
多分こんな感じでした^^;
転載先:https://www.cnblogs.com/blog-Dr-J/p/9508956.html
cさんはランニングがとても面白いと思って、「毎日走るのが好き」というゲームを作ることにしました.毎日走るのが好きなのは1つの育成类のゲームで、プレーヤーが毎日时间通りにオンラインになって、カードを打つ任务を完成する必要があります.
このゲームの地図は,N個のノードとN−1個のエッジを含むツリーと見なすことができ,各エッジが2個のノードを接続し,任意の2つのノードが1つの経路で互いに達することができる.ツリー上のノード番号は、1からNまでの連続正の整数です.
今はプレイヤーがいて、最初のプレイヤーの起点はSiで、終点はTiです.毎日カードを打つ任務が始まる時、すべてのプレーヤーは0秒目に同時に自分の起点から出発して、毎秒1本の辺の速度を走って、間断なく最短の経路に沿って自分の終点に向かって走って、終点に着いた後にそのプレーヤーはカードを打つ任務を完成しました.(地図は木なので、一人一人の経路は唯一です)
Cちゃんはゲームの活躍度が知りたくて、ノードごとにオブザーバーが置かれていました.ノードのオブザーバーは、Wj秒目にプレイヤーを観察することを選択し、1人のプレイヤーがこのオブザーバーに観察され、そのプレイヤーがWj秒目にちょうどノードJに到着したときにのみ観察することができる.Cさんはオブザーバー一人一人が何人観察するか知りたいです.
注意:あるプレイヤーが自分のゴールに着いたら、そのプレイヤーはゲームを終了すると思います.彼はしばらく待ってからオブザーバーに観察されることはできません.すなわち、ノードJを終点とするプレイヤーに対して、Wj秒目に再び終点に到達すると、ノードJのオブザーバーはそのプレイヤーを観察できない.もし彼がちょうどWj秒でゴールに着いたら、ノードのオブザーバーはこのプレイヤーを観察することができます.
入力フォーマット
1行目には2つの整数NとMがある.このうちNはツリーのノード数を表し,またオブザーバーの数を表し,Mはプレイヤーの数を表す.
次に、n−1行の2つの整数UおよびVは、ノードUからノードVまでのエッジがあることを示す.
次の行のN個の整数で、そのうちの第1の整数はWjであり、ノードがオブザーバーに現れる時間を表す.
次にM行、1行あたり2つの整数SiとTiは、1人のプレイヤーの始点と終点を表す.
すべてのデータに対して、保証します.1<=Si,Ti<=N,0<=Wj<=N
出力フォーマット
1行N個の整数を出力し,j番目の整数はノードjのオブザーバーがどれだけの人を観察できるかを示す.
問題解決の考え方:
方法一:線分ツリー+ツリーチェーン分割
まず、どのようなプレイヤーが見られるかを考えてみましょう.それは、いつプレイヤーがノードに着くかということです.
プレイヤーの初期時の位置深さをdとする.
多分、プレイヤーが上に向かって歩いていると、0時に経路上のd深さの点、1時にd-1深さの点、2時にd-2まで歩いて深さの点になります.
では、上へ行く過程で、通過点のオブザーバーは等式(w+deep)=dを成立させるだけで、プレイヤーが見えます.
同じようにプレイヤーが下を向いているときにも似たような結論があります.プレイヤーの(d-2*パス上のlcaのdeep)=(w-deep)だけで見えます.
では、線分の木を開けて保存すればいいです.
各深さの2本の線分ツリーについて、下へ行くノードと上へ行くノードの観察値、すなわち、各プレイヤーのd上の線分ツリーは、各プレイヤーが経験した点に対して+1統一される.
つまり、ツリーチェーンに+1を付けると、単一のクエリーで済むようになります.
木の鎖の上に+1、木の鎖を使って分割すればいいです^^;
線分の木は大きな空間を占めてダイナミックに開くといいです
また、浅い深さの点では、最終的な下向きのインデックスが負になる可能性があることがわかりました.そのため、下向きのセグメントツリーインデックスには3 e 5が統一されています.
多分こんな感じでした^^;
1 #include
2 #include
3 #include
4 using namespace std;
5 const int N=(int)(3e5);
6 const int T=(int)(13000000);
7 struct pnt{
8 int w;
9 int hd;
10 int dp;
11 int fa;
12 int wgt;
13 int mxs;
14 int ind;
15 int top;
16 }p[N];
17 struct ent{
18 int twd;
19 int lst;
20 }e[N*2];
21 struct sgt{
22 int ls;
23 int rs;
24 int vls;
25 }tr[T];
26 int cnt;
27 int siz;
28 int dnt;
29 int n,m;
30 int rtu[N*2],rtd[N*2];
31 int sta[N],fin[N];
32 void ade(int f,int t)
33 {
34 cnt++;
35 e[cnt].twd=t;
36 e[cnt].lst=p[f].hd;
37 p[f].hd=cnt;
38 }
39 void Tr_pushdown(int spc)
40 {
41 if(tr[spc].ls)
42 tr[tr[spc].ls].vls+=tr[spc].vls;
43 if(tr[spc].rs)
44 tr[tr[spc].rs].vls+=tr[spc].vls;
45 tr[spc].vls=0;
46 }
47 void Tr_build(int &spc,int l,int r,int plc)
48 {
49 if(!spc)
50 spc=++siz;
51 if(l==r)
52 return ;
53 int mid=(l+r)/2;
54 if(plc<=mid)
55 Tr_build(tr[spc].ls,l,mid,plc);
56 else
57 Tr_build(tr[spc].rs,mid+1,r,plc);
58 }
59
60 void Tr_add(int ll,int rr,int l,int r,int spc,int v)
61 {
62 if(!spc)
63 return ;
64 if(ll>r||l>rr)
65 return ;
66 if(ll<=l&&rr>=r)
67 {
68 tr[spc].vls+=v;
69 return ;
70 }
71 int mid=(l+r)/2;
72 Tr_add(ll,rr,l,mid,tr[spc].ls,v);
73 Tr_add(ll,rr,mid+1,r,tr[spc].rs,v);
74 return ;
75 }
76 int Tr_val(int plc,int spc,int l,int r)
77 {
78 if(!spc)
79 return 0;
80 if(l==r)
81 return tr[spc].vls;
82 Tr_pushdown(spc);
83 int mid=(l+r)/2;
84 if(plc<=mid)
85 return Tr_val(plc,tr[spc].ls,l,mid);
86 else
87 return Tr_val(plc,tr[spc].rs,mid+1,r);
88 }
89 void Basic_dfs(int x,int f)
90 {
91 p[x].fa=f;
92 p[x].dp=p[f].dp+1;
93 p[x].wgt=1;
94 int maxs=0;
95 for(int i=p[x].hd;i;i=e[i].lst)
96 {
97 int to=e[i].twd;
98 if(to==f)
99 continue;
100 Basic_dfs(to,x);
101 p[x].wgt+=p[to].wgt;
102 if(maxs<p[to].wgt)
103 {
104 maxs=p[to].wgt;
105 p[x].mxs=to;
106 }
107 }
108 }
109 void Build_dfs(int x,int tp)
110 {
111 if(!x)
112 return ;
113 p[x].ind=++dnt;
114 p[x].top=tp;
115 Tr_build(rtu[p[x].dp+p[x].w],1,n,dnt);
116 Tr_build(rtd[p[x].w-p[x].dp+N],1,n,dnt);
117 Build_dfs(p[x].mxs,tp);
118 for(int i=p[x].hd;i;i=e[i].lst)
119 {
120 int to=e[i].twd;
121 if(p[to].ind)
122 continue;
123 Build_dfs(to,to);
124 }
125 }
126 int LCA(int x,int y)
127 {
128 while(p[x].top!=p[y].top)
129 {
130 if(p[p[x].top].dp<p[p[y].top].dp)
131 swap(x,y);
132 x=p[p[x].top].fa;
133 }
134 if(p[x].dp>p[y].dp)
135 swap(x,y);
136 return x;
137 }
138 int main()
139 {
140 scanf("%d%d",&n,&m);
141 for(int i=1;i)
142 {
143 int x,y;
144 scanf("%d%d",&x,&y);
145 ade(x,y);
146 ade(y,x);
147 }
148 for(int i=1;i<=n;i++)
149 scanf("%d",&p[i].w);
150 for(int i=1;i<=m;i++)
151 scanf("%d%d",&sta[i],&fin[i]);
152 Basic_dfs(1,1);
153 Build_dfs(1,1);
154 for(int i=1;i<=m;i++)
155 {
156 int f=LCA(sta[i],fin[i]);
157 int x=sta[i];
158 int rt=p[sta[i]].dp;
159 while(p[x].top!=p[f].top)
160 {
161 Tr_add(p[p[x].top].ind,p[x].ind,1,n,rtu[rt],1);
162 x=p[p[x].top].fa;
163 }
164 Tr_add(p[f].ind,p[x].ind,1,n,rtu[rt],1);
165 Tr_add(p[f].ind,p[f].ind,1,n,rtu[rt],-1);
166 x=fin[i];
167 rt=N+p[sta[i]].dp-2*p[f].dp;
168 while(p[x].top!=p[f].top)
169 {
170 Tr_add(p[p[x].top].ind,p[x].ind,1,n,rtd[rt],1);
171 x=p[p[x].top].fa;
172 }
173 Tr_add(p[f].ind,p[x].ind,1,n,rtd[rt],1);
174 }
175 for(int i=1;i<=n;i++)
176 {
177 int dowsid=Tr_val(p[i].ind,rtd[N+p[i].w-p[i].dp],1,n);
178 int upsid=Tr_val(p[i].ind,rtu[p[i].dp+p[i].w],1,n);
179 printf("%d ",dowsid+upsid);
180 }
181 return 0;
182 }
転載先:https://www.cnblogs.com/blog-Dr-J/p/9508956.html