9-17考试 数星星

题意

给定一棵树,点带权,m个点对(m条路径),q次询问区间路径并的点权和。

$n,m,q\le 10^5$

题解

考虑移动右端点。

对每个点维护最后一个包含它的路径编号$x_i$。

询问就相当于$x_i\ge l$的点权和。

操作就相当于链推平。

树剖之后相当于链推平。

用一个类似于珂朵莉树的东西维护连续段就可以了

具体的,用set<pair<int,int> int>来维护连续段和它的$x$,每次推平l,r就相当于在l-1处拆分,r处拆分,然后把l..r的区间全部删掉,最后加一个l,r的区间就可以了

删区间加区间的时候可以用树状数组维护点权和。

时间复杂度$O(m\log^2 n)$,为啥?

每次推平最多拆两次(多两个区间),每个区间最多被删一次, 每次最多加一个区间,所以均摊$O(log(n))$一次推平(因为要用set定位),又因为要树剖所以就$O(m\log 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
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
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
/*
Author: QAQ Automaton
Lang: C++
Prog: star.cpp
Mail: lk@qaq-am.com
Blog: https://www.qaq-am.com/
*/
#include<bits/stdc++.h>
#define int long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const double eps=1e-8;
const double pi=acos(-1.0);
template<class T>int chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>int chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
template<class T>int dcmp(T a,T b){return a>b;}
template<int *a>int cmp_a(int x,int y){return a[x]<a[y];}
#define min mmin
#define max mmax
#define abs aabs
namespace io {
const int SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int f, qr;
// getchar
#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
// print the remaining part
inline void flush () {
fwrite (obuf, 1, oS - obuf, stdout);
oS = obuf;
}
// putchar
inline void putc (char x) {
*oS ++ = x;
if (oS == oT) flush ();
}
// input a signed integer
inline bool read (signed &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;else if(c==EOF)return 0;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
return 1;
}

inline bool read (long long &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;else if(c==EOF)return 0;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
return 1;
}
inline bool read (char &x) {
x=gc();
return x!=EOF;
}
inline bool read(char *x){
while((*x=gc())=='\n' || *x==' '||*x=='\r')if(*x==EOF)return 0;
while(!(*x=='\n'||*x==' '||*x=='\r'||*x==EOF))*(++x)=gc();
*x=0;
return 1;
}
template<typename A,typename ...B>
inline bool read(A &x,B &...y){
return read(x)&&read(y...);
}
// print a signed integer
inline bool write (signed x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
return 0;
}

inline bool write (long long x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
return 0;
}
inline bool write (char x) {
putc(x);
return 0;
}
inline bool write(const char *x){
while(*x){putc(*x);++x;}
return 0;
}
inline bool write(char *x){
while(*x){putc(*x);++x;}
return 0;
}
template<typename A,typename ...B>
inline bool write(A x,B ...y){
return write(x)||write(y...);
}
//no need to call flush at the end manually!
struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: read;
using io :: putc;
using io :: write;
int inf;
struct _init_{
_init_(){
memset(&inf,0x3f,sizeof(inf));
}
};
_init_ ___INIT__;
set<pair<pii,int> > st;
int n,m,q;
int bit[100005],a[100005],s[100005],tot;
void add(int x,int y){
for(;x;x^=x&-x)bit[x]=bit[x]+y;
}
int sum(int x){
int y=0;
for(;x<=n;x+=x&-x)y+=bit[x];
return y;
}

void split(int x){
if(!x)return;
auto it=st.upper_bound(make_pair(make_pair(x,inf),inf));
--it;
if(it->x.y>x){
auto w=*it;
st.erase(it);
st.insert(make_pair(make_pair(w.x.x,x),w.y));
st.insert(make_pair(make_pair(x+1,w.x.y),w.y));
}
}
void rebuild(int l,int r,int w){
split(l-1);
split(r);
while(1){
auto it=st.lower_bound(make_pair(make_pair(l,0),0));
if(it==st.end())break;
if(it->x.x>r)break;
add(it->y,s[it->x.x-1]-s[it->x.y]);
st.erase(it);
}
add(w,s[r]-s[l-1]);
st.insert(make_pair(make_pair(l,r),w));
}
int qs[100005],qt[100005],ans[100005];
vector<pii> qu[100005];
vector<int> to[100005];
int siz[100005],hvy[100005],top[100005],dis[100005];
int dfn[100005],fa[100005];
int t;
void dfs(int x,int f){
siz[x]=1;
for(auto i:to[x])if(i!=f){
dfs(i,x);
siz[x]+=siz[i];
if(siz[hvy[x]]<siz[i])hvy[x]=i;
}
}
void dfs2(int x,int f){
dfn[x]=++t;
s[t]=s[t-1]+a[x];
if(hvy[x]){
top[t+1]=top[t];
dis[t+1]=dis[dfn[x]];
dfs2(hvy[x],x);
}
for(auto i:to[x])if(i!=f && i!=hvy[x]){
top[t+1]=t+1;
fa[t+1]=dfn[x];
dis[t+1]=dis[dfn[x]]+1;
dfs2(i,x);
}
}
void work(int u,int v,int x){
u=dfn[u];v=dfn[v];
while(1){
if(top[u]==top[v]){
if(u>v)swap(u,v);
rebuild(u,v,x);
return;
}
if(dis[u]<dis[v])swap(u,v);
rebuild(top[u],u,x);
u=fa[top[u]];
}
}
signed main(){
freopen("star.in","r",stdin);
freopen("star.out","w",stdout);
read(n,m,q);
for(int i=1;i<=n;++i){read(a[i]);tot+=a[i];}
st.insert(make_pair(make_pair(1,n),0));
int u,v;
for(int i=1;i<n;++i){
read(u,v);
to[u].push_back(v);
to[v].push_back(u);
}
dfs(1,0);
top[1]=1;
dfs2(1,0);
for(int i=1;i<=m;++i){
read(qs[i],qt[i]);
}
int l,r;
for(int i=1;i<=q;++i){
read(l,r);
qu[r].push_back(make_pair(l,i));
}
for(int i=1;i<=m;++i){
work(qs[i],qt[i],i);
for(auto j:qu[i])
ans[j.y]=sum(j.x);
}
for(int i=1;i<=q;++i)write(ans[i],'\n');
return 0;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×