HDU6162 Ch's gift

给定一棵树,已知每个点点权$w_i$,每次给定$s,t,a,b$,求从s到t的路径上满足$a\le$点权$\le b$的点的点权和。

点数,询问数$\le 10^5$,多组数据,$w_i,a,b\le 10^9$

不正确做法

有一个不正确但是因为数据水可以水过去的做法:

首先树链剖分,显然剖分完要用线段树对吧。

线段树上记录一段区间的最大值和最小值以及和。

每次查找一条重链上满足条件的点权和时,首先定位这个区间,接着做判断:

设区间最小值为$Min$,最大值为$Max$,区间和为$Sum$

如果$a\le Min\le Max \le b$则全部满足,返回$Sum$

如果$Max< a$或$b < Min$则全不满足,返回0

否则递归左半区间和右半区间计算。

显然可以卡飞:

1
2
3
4
5
6
7
8
9
10
11
12
100000 100000
1 100 1 100 1 100...(wi满足1和100交替出现)
1 2
2 3
...(一条链)
1 100000 99 101
1 100000 99 101
1 100000 99 101
1 100000 99 101
1 100000 99 101
1 100000 99 101
...(全部操作全部是这样)

显然每个操作的复杂度被卡到了$O(n)$,T飞。

正确做法

正确做法是树上主席树

通过离散化,设点$i$的权值为$w_i$,排名为$rk_i$($w_i$相同的点算一个点)

设$s_{i,j}$表示从$i$到根这一条路径上满足$rk_s=j$的i的$w_i$和。

然后强行建可持久化主席树。

显然满足满足$a\le w_s \le b$的点的点s满足$rk_s$在一段区间$[l,r]$里,并且当$rk_s<l$或$r<rk_s$时$w_s<a$或$b<w_s$

然后找出$l,r$

显然从i到根满足$a\le$点权$\le b$的点的点权和$Answer_i$是$\sum_{j=l}^rs_{i,j}$

从s到t满足条件的点的点权和为$Answer_s+Answer_t-Answer_l-Answer_{fa}$

其中l为$LCA(s,t)$,$fa$为$l$的父亲节点。

答案可能爆int,无脑全开ll爆内存,空间限制差评。

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
/*
Author: CNYALI_LK
LANG: C++
PROG: 6162.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
using namespace std;
const double eps=1e-8;
const double PI=acos(-1.0);
typedef long long ll;
template<class T>ll chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>ll 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;}
#define min mmin
#define max mmax
#define abs aabs
ll read(){
ll s=0,base=1;
char c;
while(!isdigit(c=getchar()))if(c=='-')base=-base;else if(c==EOF)exit(0);
while(isdigit(c)){s=s*10+(c^48);c=getchar();}
return s*base;
}
char WritellBuffer[1024];
template<class T>void write(T a,char end){
ll cnt=0,fu=1;
if(a<0){putchar('-');fu=-1;}
do{WritellBuffer[++cnt]=fu*(a%10)+'0';a/=10;}while(a);
while(cnt){putchar(WritellBuffer[cnt]);--cnt;}
putchar(end);
}
ll c[102424],l[102424],d[102424];
int ls[2000876],rs[2000876];
ll cnt[2000876],tot;
ll root[102424];
ll to[233333],lst[233333],beg[102424],e;
void ADD(ll u,ll v){
to[++e]=v;
lst[e]=beg[u];
beg[u]=e;
to[++e]=u;
lst[e]=beg[v];
beg[v]=e;
}
int fa[18][102424],t;
#define mid ((l+r)>>1)
ll newtree(ll l,ll r,ll d,ll c){
ll k=++tot;
cnt[tot]=(l<=d&&d<=r)*c;
if(l==r){
ls[k]=rs[k]=0;
return k;
}
ls[k]=newtree(l,mid,d,c);
rs[k]=newtree(mid+1,r,d,c);
return k;
}
ll make(ll x){
return newtree(1,t,d[x],c[x]);
}
ll copy(ll fa,ll x){
ll l=1,r=t,k=tot+1,s=root[fa];
while(l<=r){
++tot;
cnt[tot]=cnt[s]+c[x];
ls[tot]=ls[s];
rs[tot]=rs[s];
if(l==r)return k;
if(d[x]<=mid){
ls[tot]=tot+1;
s=ls[s];
r=mid;
}
else {
rs[tot]=tot+1;
s=rs[s];
l=mid+1;

}
}
return k;
}
ll dep[102424];
void dfs(ll x,ll f){
dep[x]=dep[f]+1;
fa[0][x]=f;
if(!f){
root[x]=make(x);
}
else root[x]=copy(f,x);
for(ll i=beg[x];i;i=lst[i])if(to[i]!=f)dfs(to[i],x);
}
ll lca(ll u,ll v){
if(dep[u]<dep[v])swap(u,v);
for(ll i=17;i+1;--i){
if(dep[fa[i][u]]>=dep[v])u=fa[i][u];
}
for(ll i=17;i+1;--i){
if(fa[i][u]!=fa[i][v])u=fa[i][u],v=fa[i][v];
}
if(u!=v)return fa[0][u];
else return u;
}
ll sum(ll x,ll l,ll r,ll lx,ll rx){
// debug("SBYJM %lld,%lld,%lld,%lld,%lld\n",x,l,r,lx,rx);
if(lx<=l&&r<=rx)return cnt[x];
if(r<lx||rx<l)return 0;
return sum(ls[x],l,mid,lx,rx)+sum(rs[x],mid+1,r,lx,rx);
}
ll js(ll x,ll l,ll r){
if(!x)return 0;
ll S=sum(root[x],1,t,l,r);
// printf("(%lld)\n",S);
return S;

}
int main(){
#ifdef cnyali_lk
freopen("6162.in","r",stdin);
freopen("6162.out","w",stdout);
#endif
ll n,m;
while(n=read()){
m=read();
for(ll i=1;i<=n;++i){
c[i]=read();
l[i]=c[i];
}
sort(l+1,l+n+1);
t=unique(l+1,l+n+1)-(l+1);
for(ll i=1;i<=n;++i){
d[i]=lower_bound(l+1,l+t+1,c[i])-l;
// printf("%lld->%lld\n",c[i],d[i]);
beg[i]=0;
}
e=0;
for(ll i=1;i<n;++i){
ADD(read(),read());
}
tot=0;
// debug("SBYJM\n");
dfs(1,0);
/// for(ll i=1;i<=n;++i)printf("%lld\n",fa[0][i]);
// debug("SBYJM\n");
for(ll i=1;i<=17;++i)for(ll j=1;j<=n;++j)fa[i][j]=fa[i-1][fa[i-1][j]];
ll S,T,d,u;
while(m){
--m;
// debug("SBYJM\n");
S=read();T=read();d=read();u=read();
// printf("%lld,%lld,%lld,%lld\n",S,T,d,u);

u=upper_bound(l+1,l+t+1,u)-l-1;
d=lower_bound(l+1,l+t+1,d)-l;
// printf("%lld,%lld\n",d,u);
ll L=lca(S,T);
write(js(S,d,u)+js(T,d,u)-js(L,d,u)-js(fa[0][L],d,u),m?' ':'\n');

// debug("sbYJM\n");
}
// debug("SBYJM\n");
}
return 0;
}

评论

Your browser is out-of-date!

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

×