當前位置：首頁 > 人文社科 > 生活经验 >内容正文

生活经验

BZOJ 4009 接水果

發布時間：2023/11/27 生活经验 32 豆豆

生活随笔收集整理的這篇文章主要介紹了 BZOJ 4009 接水果小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

Description

風見幽香非常喜歡玩一個叫做osu!的游戲，其中她最喜歡玩的模式就是接水果。
由于她已經DT FC了The big black, 她覺得這個游戲太簡單了，于是發明了一個更加難的版本。首先有一個地圖，是一棵由\(n\)個頂點、\(n-1\)條邊組成的樹。這顆樹上有\(P\)個盤子，每個盤子實際上是一條路徑，并且每個盤子還有一個權值。第\(i\)個盤子就是頂點\(a_{i}\)到頂點\(b_{i}\)的路徑(由于是樹，所以從\(a_{i}\)到\(b_{i}\)的路徑是唯一的)，權值為\(c_{i}\)。接下來依次會有\(Q\)個水果掉下來，每個水果本質上也是一條路徑，第\(i\)個水果是從頂點\(u_{i}\)到頂點\(v_{i}\)的路徑。幽香每次需要選擇一個盤子去接當前的水果：一個盤子能接住一個水果，當且僅當盤子的路徑是水果的路徑的子路徑。這里規定:從\(a\)到\(b\)的路徑與從\(b\)到\(a\)的路徑是同一條路徑。當然為了提高難度，對于第\(i\)個水果，你需要選擇能接住它的所有盤子中，權值第\(k_{i}\)小的那個盤子，每個盤子可重復使用（沒有使用次數的上限：一個盤子接完一個水果后，后面還可繼續接其他水果，只要它是水果路徑的子路徑）。幽香認為這個游戲很難，你能輕松解決給她看嗎？

Input

第一行三個數\(n,P\)和\(Q\)，表示樹的大小和盤子的個數和水果的個數。
接下來\(n-1\)行，每行兩個數\(a,b\)，表示樹上的\(a\)和\(b\) 之間有一條邊。樹中頂點按\(1\)到\(n\)標號。接下來\(P\)行，每行三個數\(a,b,c\)，表示路徑為\(a\)到\(b\)、權值為\(c\)的盤子，其中\(0 \le c \le 10^{9},a \neq b\)。
接下來\(Q\)行，每行三個數\(u,v,k\)，表示路徑為\(u\)到\(v\)的水果，其中\(u \neq v\)，你需要選擇第\(k\)小的盤子，第\(k\)小一定存在。

Output

對于每個果子，輸出一行表示選擇的盤子的權值。

Sample Input

10 10 10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
3 2 217394434
10 7 13022269
6 7 283254485
6 8 333042360
4 6 442139372
8 3 225045590
10 4 922205209
10 8 808296330
9 2 486331361
4 9 551176338
1 8 5
3 8 3
3 8 4
1 8 3
4 8 1
2 3 1
2 3 1
2 3 1
2 4 1
1 4 1

Sample Output

442139372
333042360
442139372
283254485
283254485
217394434
217394434
217394434
217394434
217394434

Hint

\(N,P,Q \le 40000\)。

整體二分。對于區間\(l \sim r\)，二分值域\(mid\)，將\(\le mid\)的盤子加入，每個水果的\(k\)與其路徑上存在的盤子數進行比較，若多了該詢問往左區間\(l \sim mid\)遞歸，否則往右區間\(mid+1 \sim r\)遞歸。
現在的問題就是如何判定每個水果的\(k\)與其路徑上存在的盤子數的大小關系?？紤]每個盤子，覆蓋的路徑為\(a_{i}\)到\(b_{i}\)（\(dep_{a_{i}} < dep_{b_{i}}\)），那么這個盤子所貢獻的水果只有可能兩種情況：
\(1.b_{i}\)在\(a_{i}\)的子樹內，那么水果的兩個端點\(u,v\)必須一個\(b_{i}\)的子樹內，一個在\(a_{i}\)的子樹外（可以包括\(a_{i}\)）。
\(2.\)否則，兩個點必須一個在\(a_{i}\)的子樹內，一個在\(b_{i}\)的子樹內。
看到有子樹的東西，馬上想到dfs序。由于這個dfs序是一段連續的區間，所以我們可以將盤子根據dfs序抽象成為矩形（情況一上兩個不相交的矩形，情況二是一個矩形），將水果抽象成為一個點，每次檢驗即詢問點被多少矩形所覆蓋。掃描線+樹狀數組即可解決。
注意：矩形必須保證\(x\)坐標小于\(y\)坐標。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
using namespace std;#define maxn (40010)
int N,P,Q,side[maxn],next[maxn*2],toit[maxn*2],dep[maxn],tree[maxn];
int L[maxn],R[maxn],ans[maxn],f[maxn][20],Ts,cnt,tot,have[maxn],sum[maxn];
struct SCAN
{int X,Y1,Y2,sign,be;friend inline bool operator <(const SCAN &a,const SCAN &b) { return a.X != b.X?a.X < b.X:a.sign<b.sign; }
}bac[8*maxn],save[maxn][4];inline int jump(int a,int step)
{for (int i = 0;step;step >>= 1,++i) if (step&1) a = f[a][i];return a;
}inline int lowbit(int a) { return a&-a; }
inline void modify(int a,int b) { for (;a <= N;a += lowbit(a)) tree[a] += b; }
inline int calc(int a) { int ret = 0; for (;a;a -= lowbit(a)) ret += tree[a]; return ret; }struct NODE
{int a,b,c,id;friend inline bool operator <(const NODE &x,const NODE &y) { return x.c < y.c; }inline void read(int i) { scanf("%d %d %d",&a,&b,&c); id = i; }inline void update() { if (L[a] > L[b]) swap(a,b); }inline void ins1() { bac[++tot] = (SCAN){L[a],L[b],L[b],0,id}; }inline void ins2() { for (int i = 0;i < have[id];++i) bac[++tot] = save[id][i]; }inline void change(){if (L[b] >= L[a]&&L[b] <= R[a]){int son = jump(b,dep[b]-dep[a]-1);if (L[son] > 1){save[id][have[id]++] = (SCAN){1,L[b],R[b],-1,id};save[id][have[id]++] = (SCAN){L[son]-1,L[b],R[b],1,id};}if (R[son] < N){save[id][have[id]++] = (SCAN){L[b],R[son]+1,N,-1,id};save[id][have[id]++] = (SCAN){R[b],R[son]+1,N,1,id};}}else{save[id][have[id]++] = (SCAN){L[a],L[b],R[b],-1,id};save[id][have[id]++] = (SCAN){R[a],L[b],R[b],1,id};}}
}path[maxn],query[maxn],tmp[maxn];inline void add(int a,int b) { next[++cnt] = side[a]; side[a] = cnt; toit[cnt] = b; }
inline void ins(int a,int b) { add(a,b); add(b,a); }inline void dfs(int now)
{L[now] = ++Ts;for (int i = 1;(1 << i) <= dep[now];++i) f[now][i] = f[f[now][i-1]][i-1];for (int i = side[now];i;i = next[i])if (toit[i] != f[now][0])f[toit[i]][0] = now,dep[toit[i]] = dep[now]+1,dfs(toit[i]);R[now] = Ts;
}inline void census(int ql,int qr,int pl,int pr,int &ll,int &rr)
{tot = 0;for (int i = pl;i <= pr;++i) path[i].ins2();for (int i = ql;i <= qr;++i) query[i].ins1();sort(bac+1,bac+tot+1);for (int i = 1;i <= tot;++i){if (!bac[i].sign) sum[bac[i].be] = calc(bac[i].Y1);else modify(bac[i].Y1,-bac[i].sign),modify(bac[i].Y2+1,bac[i].sign);}for (int i = ql;i <= qr;++i){if (sum[query[i].id] >= query[i].c) tmp[++ll] = query[i];else query[i].c -= sum[query[i].id],tmp[--rr] = query[i];sum[query[i].id] = 0;}for (int i = ql;i <= qr;++i) query[i] = tmp[i];for (int i = 1;i <= tot;++i)if (bac[i].sign) modify(bac[i].Y1,bac[i].sign),modify(bac[i].Y2+1,-bac[i].sign);
}inline void work(int ql,int qr,int pl,int pr)
{if (ql > qr) return;if (pl == pr){for (int i = ql;i <= qr;++i) ans[query[i].id] = path[pl].c;return;}int ll = ql-1,rr = qr+1,mid = (pl + pr)>>1;census(ql,qr,pl,mid,ll,rr);work(ql,ll,pl,mid); work(rr,qr,mid+1,pr);
}int main()
{freopen("fruit.in","r",stdin);freopen("fruit.out","w",stdout);scanf("%d %d %d",&N,&P,&Q);for (int i = 1,a,b;i < N;++i) scanf("%d %d",&a,&b),ins(a,b);dfs(1);for (int i = 1;i <= P;++i) path[i].read(i),path[i].update(),path[i].change();sort(path+1,path+P+1);for (int i = 1;i <= Q;++i) query[i].read(i),query[i].update();work(1,Q,1,P);for (int i = 1;i <= Q;++i) printf("%d\n",ans[i]);fclose(stdin); fclose(stdout);return 0;
}

轉載于:https://www.cnblogs.com/mmlz/p/4448719.html

總結

以上是生活随笔為你收集整理的BZOJ 4009 接水果的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

bzoj
水果