ATP大爷在做题, 我偷偷地瞥了一眼。

发现自己只会\(O(n \log^2 n)\)的愚蠢做法。

问ATP大爷行不行, ATP大爷表示已经有\(O(\log n)\)做法, 我的做法太垃圾了。。。

但是我卡了一波常数。就rk3了。。

题目大意

\(n\)个点,形成一个树状结构。有\(m\)次发放,每次选择两个点\((x,y)\)

对于\(x\)\(y\)的路径上每个点发一袋\(z\)类型的物品。完成所有发放后,每个点存放最多的是哪种物品。

解题报告

把每次发放, 用树链剖分转成\(\log n\)次序列上的操作, 然后利用扫描线扫描一波。

用线段树维护每个物品在扫描线的当前位置出现次数最多的位置。

因为是单点修改, 全局查询, 所以用一个非递归的线段树就可以了。

而且查询是\(O(1)\)的。

复杂度是\(O(n \log^2 n + n)\)

这个。 跑得不慢。内存比较优秀(\(O(n)\)), 代码长度比较可爱。

但是网上好像都是线段树合并啊。。

代码

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
using namespace std;
#define rep(i,a,b) for(int i=int(a),nn=int(b);i<=nn;++i)
#define vep(i,a,b) for(int i=int(a),nn=int(b);i>=nn;--i)
#define xep(i,b) for(int i=0,nn=int(b);i<nn;++i)
#define pb push_back
#define sz(x) (int)(x.size())
#define mp make_pair
#define fi first
#define se second
const int N = 100100;
typedef pair<int,int> ii;
int v[N], a[N], mx[N<<2];
int vc[N], vn;
int hd[N], nx[N<<1], ri[N<<1], al;
int fa[N], de[N], sn[N], sz[N];
int bl[N], dn[N], bd[N], ss;
vector<ii> ad[N];
int n, m, _;
char *cp=(char *)malloc(32747), *os=cp, *ot=cp;
#define getc() (os==ot&&(ot=(os=cp)+fread(cp,1,32747,stdin),os==ot)?0:*os++)
inline void in(int &x) {
char c=getc(); int f=1;
for (;c <'0' ||c >'9'; c=getc()) f=(c=='-'?-1:f);
for (x=0; c >='0'&&c<='9'; c=getc()) x=x*10+c-48;
x *= f;
}
#define add(x, y) nx[++al]=hd[x],ri[al]=y,hd[x]=al
#define up(o) mx[o]=(a[mx[o<<1|1]]>a[mx[o<<1]]?mx[o<<1|1]:mx[o<<1])
void dfs(int x) {
int y = 0;
de[x] = de[fa[x]] + 1;
sz[x] = 1, sn[x] = 0;
for (int i=hd[x];i;i=nx[i])
if (y=ri[i], y!=fa[x]) {
fa[y] = x, dfs(y);
sz[x] = sz[x] + sz[y];
if (sz[y] > sz[sn[x]])
sn[x] = y;
}
}
void dfs(int x, int tp) {
bl[x] = tp, dn[x] = ++ss, bd[ss] = x;
if (sn[x]) {
dfs(sn[x], tp);
int y;
for (int i=hd[x];i;i=nx[i])
if (y=ri[i], y!=fa[x] && y!=sn[x])
dfs(y, y);
}
}
void ins(int x,int y) {
int fx = bl[x], fy = bl[y];
int v = vn-1;
while (fx != fy) {
if (de[fx] < de[fy])
swap(fx, fy), swap(x, y);
ad[dn[fx]].pb(mp(v,1));
ad[dn[x]+1].pb(mp(v,-1));
x = fa[fx], fx = bl[x];
}
if (de[x] > de[y]) swap(x,y);
ad[dn[x]].pb(mp(v,1));
ad[dn[y]+1].pb(mp(v,-1));
}
void print(int x) {
if (x) print(x/10), putchar(x%10+48);
}
void out(int x) {
if (!x) puts("0");
else print(x), puts("");
}
int main() {
in(n), in(m);
int x, y, z;
xep(i, n-1) {
in(x), in(y);
add(x,y), add(y,x);
}
dfs(1), dfs(1, 1);
xep(i, m) {
in(x), in(y), in(z);
v[vn++] = z;
vc[vn-1] = z;
ins(x, y);
}
sort(vc, vc+vn);
vn = unique(vc,vc+vn)-vc;
xep(i, m) v[i] = lower_bound(vc, vc+vn, v[i])-vc;
for (_ = 1; _<vn; _=_<<1);
rep(i, _, _*2-1) mx[i] = i-_;
vep(i, _-1, 1) up(i);
static int as[N];
rep(i, 1, n) {
xep(j, sz(ad[i])) {
x = ad[i][j].fi, z = ad[i][j].se;
x = v[x], a[x] = a[x] + z;
y = _+x;
for (y>>=1; y; y>>=1) up(y);
}
as[bd[i]] = (a[mx[1]]?vc[mx[1]]:0);
}
rep(i, 1, n) out(as[i]);
return 0;
}

留言