HNOI2015 接水果

Source and Judge

HNOI2015 接水果

Record

1h

Analysis

请先思考后再展开

目前见过最难的整体二分了,但也不是很难,可能是我刷题太少

包含这东西,很显然可以化化式子,然后就是dfs序的一个矩形

问题转化为,求每个点,覆盖它的矩形中,第k大的
整体第k大的查询,就是很套路
二分以后,重点就是check,用小于mid的部分,询问被多少个覆盖掉
那这个暴力搞得话例如cdq、树套树什么的……但都太复杂了没细想
其实,重点在于它是一个矩形,可以扫描线搞

例如说拆成左线段和右线段,然后就变成修改和查询,然后就树状数组询问次数就好了

顺便提供一份反例代码,改成盘子是水果的父路径
看错题的自我安慰:能出题

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
//Zory-2018
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
#ifdef DEBUG
const int LOCAL=1;
#else
const int LOCAL=0;
#endif
namespace mine
{
typedef long long ll;
const int INF=0x3f3f3f3f;
int bin[30];
const int MAX_N=41000;
struct Bit
{
int bit[MAX_N];
Bit(){memset(bit,0,sizeof bit);}
int lowbit(int x) {return x&-x;}
void change(int x,int c)
{
while(x<MAX_N) bit[x]+=c,x+=lowbit(x);
}
int sum(int x)
{
int ans=0;
while(x>=1) ans+=bit[x],x-=lowbit(x);
return ans;
}
}bit;
struct Tree
{
int n;
int hou[MAX_N],dfn[MAX_N],siz[MAX_N],dep[MAX_N];
struct Edge{int y,g;}e[MAX_N*2];
int ln,id;Tree(){memset(hou,0,sizeof hou);dep[0]=0;ln=id=0;}
void ins(int x,int y) {e[++ln]=(Edge){y,hou[x]};hou[x]=ln;}
int f[MAX_N][30];
void dfs(int x,int fa)
{
dfn[x]=++id;siz[x]=1;dep[x]=dep[fa]+1;
f[x][0]=fa;for(int i=1;i<=20;i++) f[x][i]=f[ f[x][i-1] ][i-1];
for(int k=hou[x];k>0;k=e[k].g)
{
int y=e[k].y;if(y==fa) continue;
dfs(y,x);siz[x]+=siz[y];
}
}
int lca(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
for(int i=20;i>=0;i--) if(dep[x]-dep[y]>=bin[i]) x=f[x][i];
if(x==y) return x;
for(int i=20;i>=0;i--) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
return f[x][0];
}
int jump(int x,int t)
{
for(int i=20;i>=0;i--) if(t&bin[i]) x=f[x][i];
return x;
}
}tr;
struct Nod
{
int a,b,c;
int fm;
int tmp;
}pt[2*MAX_N],qes[MAX_N],tmp1[MAX_N*2],tmp2[MAX_N*2];
bool cmp(Nod a,Nod b) {return a.a<b.a;}
struct Qes
{
int a,b;
int fm,xx;
}q[MAX_N*8];
bool cmp2(Qes a,Qes b) {return a.a<b.a;}
int cnt;
void add(int a,int b,int c,int d,int fm)
{
if(a>b or c>d) return;
if(a-1>0 and c-1>0) q[++cnt]=(Qes){a-1,c-1,fm,1};
if(c-1>0) q[++cnt]=(Qes){b,c-1,fm,-1};
if(a-1>0) q[++cnt]=(Qes){a-1,d,fm,-1};
q[++cnt]=(Qes){b,d,fm,1};
}
int ans[MAX_N],tans[MAX_N];
void solve(int fl,int fr,int ql,int qr,int pl,int pr)
{
if(ql>qr or pl>pr) return;
if(fl==fr)
{
for(int i=ql;i<=qr;i++) ans[qes[i].fm]=fl;
return;
}
if(pl==pr)
{
for(int i=ql;i<=qr;i++) ans[qes[i].fm]=pt[pl].c;
return;
}
int mid=(fl+fr)/2;
int tot1=0,tot2=0;
for(int i=pl;i<=pr;i++)
if(pt[i].c<=mid) tmp1[++tot1]=pt[i];
else tmp2[++tot2]=pt[i];
for(int i=1;i<=tot1;i++) pt[pl+i-1]=tmp1[i];
for(int i=1;i<=tot2;i++) pt[pl+tot1+i-1]=tmp2[i];
int left=tot1;
//两边内部仍有序
cnt=0;
for(int i=ql;i<=qr;i++)
{
int a=qes[i].a,b=qes[i].b,t=qes[i].tmp;
if(t)
{
add(1,tr.dfn[t]-1, tr.dfn[b],tr.dfn[b]+tr.siz[b]-1,i);
add(tr.dfn[t]+tr.siz[t],tr.n,tr.dfn[b],tr.dfn[b]+tr.siz[b]-1,i);
}
else add(tr.dfn[a],tr.dfn[a]+tr.siz[a]-1,tr.dfn[b],tr.dfn[b]+tr.siz[b]-1,i);
}
sort(q+1,q+cnt+1,cmp2);
int t=pl-1;
for(int i=ql;i<=qr;i++) tans[i]=0;
for(int i=1;i<=cnt;i++)
{
while(t+1<=pl+tot1-1 and pt[t+1].a<=q[i].a) bit.change(pt[++t].b,1);
//printf("t=%d\n",t);
tans[q[i].fm]+=q[i].xx*bit.sum(q[i].b);
}
for(int i=pl;i<=t;i++) bit.change(pt[i].b,-1);
tot1=0,tot2=0;
for(int i=ql;i<=qr;i++)
{
if(qes[i].c<=tans[i]) tmp1[++tot1]=qes[i];
else qes[i].c-=tans[i],tmp2[++tot2]=qes[i];//debug 顺序……
}
for(int i=1;i<=tot1;i++) qes[ql+i-1]=tmp1[i];
for(int i=1;i<=tot2;i++) qes[ql+tot1+i-1]=tmp2[i];
solve(fl,mid,ql,ql+tot1-1,pl,pl+left-1);
solve(mid+1,fr,ql+tot1,qr,pl+left,pr);
}
void main()
{
bin[0]=1;for(int i=1;i<=20;i++) bin[i]=bin[i-1]<<1;
int pp,qq;scanf("%d%d%d",&tr.n,&pp,&qq);
for(int i=1;i<=tr.n-1;i++)
{
int x,y;scanf("%d%d",&x,&y);
tr.ins(x,y);tr.ins(y,x);
}
tr.dfs(1,0);
for(int i=1;i<=pp;i++)
{
int a,b,c;scanf("%d%d%d",&a,&b,&c);
a=tr.dfn[a],b=tr.dfn[b];
pt[2*i-1]=(Nod){a,b,c,0,0};
pt[2*i]=(Nod){b,a,c,0,0};
//一次只会计算到一个
}
sort(pt+1,pt+pp*2+1,cmp);
for(int i=1;i<=qq;i++)
{
int a,b,c;scanf("%d%d%d",&a,&b,&c);
if(tr.dep[a]>tr.dep[b]) swap(a,b);
//a->t->b在一条竖直的链上
qes[i]=(Nod){a,b,c,i,(tr.lca(a,b)==a)?tr.jump(b,tr.dep[b]-tr.dep[a]-1):0};
}
solve(0,1e9,1,qq,1,2*pp);
for(int i=1;i<=qq;i++) printf("%d\n",ans[i]);
}
};
int main()
{
srand(time(0));
mine::main();
}

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