【NOIP16 D1T2】天天爱跑步

Source and Judge

NOIP2016 提高组 D1T2
Loj2359
Uoj261
Bzoj4719
Luogu1600
Caioj1576

Problem

【Description】
小C同学认为跑步非常有趣,于是决定制作一款叫做《天天爱跑步》的游戏。《天天爱跑步》是一个养成类游戏,需要玩家每天按时上线,完成打卡任务。

这个游戏的地图可以看作一棵包含n个结点和n - 1条边的树,每条边连接两个结点,且任意两个结点存在一条路径互相可达。树上结点编号为从1到n的连续正整数。

现在有m个玩家,第i个玩家的起点为Si,终点为Ti。每天打卡任务开始时,所有玩家 在第0秒 同时从 自己的起点 出发,以 每秒跑一条边 的速度,不间断地沿着最短路径向着 自己的终点 跑去,跑到终点后该玩家就算完成了打卡任务。(由于地图是一棵树,所以每个人的路径是唯一的)

小C想知道游戏的活跃度,所以在每个结点上都放置了一个观察员。在结点j的观察员会选择在第Wj秒观察玩家,一个玩家能被这个观察员观察到当且仅当该玩家在第Wj秒也 正好 到达了结点j。小C想知道每个观察员会观察到多少人?

注意: 我们认为一个玩家到达自己的终点后该玩家就会结束游戏,他不能等待一段时间后再被观察员观察到。即对于把结点j作为终点的玩家:若他在第Wj秒前到达 终点,则在结点j的观察员 不能观察到 该玩家;若他 正好 在第Wj秒到达终点,则在结点j的观察员 可以观察到 这个玩家。
【Input】
第一行有两个整数n和m。其中n代表树的结点数量,同时也是观察员的数量, m代表玩家的数量。
接下来n - 1行每行两个整数u和v,表示结点u到结点v有一条边。
接下来一行n个整数,其中第j个整数为Wj,表示结点j出现观察员的时间。 接下来m行,每行两个整数Si和Ti,表示一个玩家的起点和终点。
【Output】
输出1行n个整数,第j个整数表示结点j的观察员可以观察到多少人。
【Limited conditions】
对于所有的数据,保证1 <= Si, Ti <= n,0 <= Wj <= n。

【Sample input 1】
6 3
2 3
1 2
1 4
4 5
4 6
0 2 5 1 2 3
1 5
1 3
2 6
【Sample output 1】
2 0 0 1 1 1
【Sample input 2】
5 3
1 2
2 3
2 4
1 5
0 1 0 3 0
3 1
1 4
5 5
【Sample output 2】
1 2 1 0 1
【Sample explanation】

Record

5h

Analysis

请先思考

首先,树上路径可以分割为两条链
咱们推一推式子吧,d是深度
向上:$d_y+w_y=d_x$
向下:$w_y-d_y=d_x-2\times d_{lca}$

然后发现就是两种值的维护,然后分上下讨论
但是怎么维护呢?

我在晚修的时候忽然想到一种奇淫巧技
用到了vector(不喜欢也可以写链表)
把上面说的维护的两种值,按照值本身分成数组,
然后我们要的就是对同值的编号,对于链上的部分,出现次数+1

那么我是使用树链剖分来搞的
用线段树维护的话,空间复杂度是很高的
使用灵活的差分,看起来还是一样,但其实我们可以运用vector的特点了,那就是实际总空间非常小,然后定位的话,就是得到了l和r之后,在保证编号有序的情况下,二分查找一下就好了

那么最后的时候递推一下,累计一下答案,这道题就完成了
但是其实细节还是很多的
例如一开始忘记对两种情况分开维护之类

现在我们分析一下复杂度
空间:$O(n)$,常数10以内
时间:$O(nlogn)$,常数3以内吧大概
然而这样优秀的时间复杂度,居然不是很快?好像有些oj还会超时……
好迷啊,之前那几个数据结构题也是类似的感觉,nlogn巨慢

Code

请先思考
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
//Zory in 2018
//*******************头文件*******************
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<set>
#include<string>
#include<queue>
#include<algorithm>
#include<iostream>
using namespace std;
int mymin(int x,int y) {return x<y?x:y;}
int mymax(int x,int y) {return x>y?x:y;}
//*******************全局常量*******************
const int MAXN=310000;
//*******************全局定义*******************
struct Nod
{
int hou;
int dep;
int siz;
int son,tp,fa;
}p[MAXN];
struct Edge
{
int y,g;
}e[MAXN*2];
int ln=0;
void ins(int x,int y)
{
e[++ln]=(Edge){y,p[x].hou};
p[x].hou=ln;
}
int w[MAXN];
int ans[MAXN];//按dfs序
//*******************实现*******************
void pre(int x,int fa)
{
p[x].fa=fa;
p[x].dep=p[fa].dep+1;
p[x].siz=1;
for(int k=p[x].hou;k>0;k=e[k].g)
{
int y=e[k].y;if(y==fa) continue;
pre(y,x);
p[x].siz+=p[y].siz;
if(p[y].siz>p[p[x].son].siz) p[x].son=y;
}
}
int id=0;
int pos[MAXN],pos2[MAXN];//dfs序编号、原编号
int getlca(int x,int y)
{
while(p[x].tp!=p[y].tp)
{
if(p[p[x].tp].dep<p[p[y].tp].dep) swap(x,y);
x=p[p[x].tp].fa;
}
return (p[x].dep<p[y].dep)?x:y;
}
void poufen(int x,int tp)
{
pos[x]=++id;pos2[id]=x;p[x].tp=tp;
if(p[x].son>0) poufen(p[x].son,p[x].tp);
for(int k=p[x].hou;k>0;k=e[k].g)
{
int y=e[k].y;
if(y!=p[x].fa and y!=p[x].son) poufen(y,y);
}
}
vector<int> upbh[MAXN*2],downbh[MAXN*2];//编号
vector<int> upcf[MAXN*2],downcf[MAXN*2];//差分
void solve()
{
int st,ed;scanf("%d%d",&st,&ed);
int up=p[st].dep+MAXN,down=p[st].dep-2*p[getlca(st,ed)].dep+MAXN;
while(p[st].tp!=p[ed].tp)
{
if(p[p[st].tp].dep>p[p[ed].tp].dep)//向上
{
int l=lower_bound(upbh[up].begin(),upbh[up].end(),pos[p[st].tp])-upbh[up].begin();
int r=upper_bound(upbh[up].begin(),upbh[up].end(),pos[st])-upbh[up].begin()-1;
upcf[up][l]++;
upcf[up][r+1]--;
st=p[p[st].tp].fa;
}
else//向下
{
int l=lower_bound(downbh[down].begin(),downbh[down].end(),pos[p[ed].tp])-downbh[down].begin();
int r=upper_bound(downbh[down].begin(),downbh[down].end(),pos[ed])-downbh[down].begin()-1;
downcf[down][l]++;
downcf[down][r+1]--;
ed=p[p[ed].tp].fa;
}
}
if(p[st].dep>p[ed].dep)//向上
{
int l=lower_bound(upbh[up].begin(),upbh[up].end(),pos[ed])-upbh[up].begin();
int r=upper_bound(upbh[up].begin(),upbh[up].end(),pos[st])-upbh[up].begin()-1;
upcf[up][l]++;
upcf[up][r+1]--;
}
else//向下
{
int l=lower_bound(downbh[down].begin(),downbh[down].end(),pos[st])-downbh[down].begin();
int r=upper_bound(downbh[down].begin(),downbh[down].end(),pos[ed])-downbh[down].begin()-1;
downcf[down][l]++;
downcf[down][r+1]--;
}
}
//*******************主函数*******************
int main()
{
memset(p,0,sizeof(p));
int n,m;scanf("%d%d",&n,&m);
for(int i=1;i<=n-1;i++)
{
int x,y;scanf("%d%d",&x,&y);
ins(x,y);ins(y,x);
}
pre(1,0);poufen(1,1);
for(int i=1;i<=n;i++) scanf("%d",&w[i]);
for(int i=1;i<=n;i++)
{
int x=pos2[i];
int w1=w[x]+p[x].dep+MAXN;if(w1<2*MAXN) upbh[w1].push_back(i),upcf[w1].push_back(0);
int w2=w[x]-p[x].dep+MAXN;if(w2<2*MAXN) downbh[w2].push_back(i),downcf[w2].push_back(0);
}
for(int i=0;i<2*MAXN;i++)//debug upper_bound找不到
{
upbh[i].push_back(MAXN-1),upcf[i].push_back(0);
downbh[i].push_back(MAXN-1),downcf[i].push_back(0);
}
for(int i=1;i<=m;i++) solve();
for(int i=0;i<2*MAXN;i++)
{
int now=0,sz;
sz=upbh[i].size();
for(int j=0;j<sz;j++)
{
now+=upcf[i][j];
ans[ upbh[i][j] ]+=now;
}
sz=downbh[i].size();
for(int j=0;j<sz;j++)
{
now+=downcf[i][j];
ans[ downbh[i][j] ]+=now;
}
}
for(int x=1;x<=n;x++) printf("%d ",ans[pos[x]]);
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/2018-05/天天爱跑步.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%