P3242 HNOI2015 接水果

2022-09-22 20:18:18 字數 1718 閱讀 3071

p3242 hnoi2015接水果

分塊求區間第k小,然後用樹上莫隊(尤拉序分塊,特判lca)做(這個做法可能會被卡,不過莫隊被卡應該很正常吧?)

令離散化後值域為 \(c_\)

利用分塊可以把求第k小的複雜度降到 \(o(\sqrt})\) 也就是 \(o(\sqrt)\)

然後就是樹上莫隊基本操作。

順便一提,分塊求第k小可以去做 這道題

#include #include #include #include #include #include using namespace std;

typedef long long ll;

const ll maxn = 1e6+10;

ll n, p, q, head[maxn], siz, c[maxn], cv[2000], cnt = -1, out[maxn] ,in[maxn], block[maxn], num, fa[22][maxn], dep[maxn];

ll seq[maxn], tot, vis[maxn], vsiz, vtot, vblock[maxn], ans[maxn], val[maxn], st[2000], ed[2000], used[maxn];

vector v[maxn], q;

struct edg e[maxn];

struct ask

} a[maxn];

void add(ll, ll);

void calc(ll);

void dfs(ll, ll);

ll gtn(ll);

ll lca(ll, ll);

int main()

for (ll x, y, v, i = 1; i <= p; i++)

sort(q.begin(), q.end());

q.erase(unique(q.begin(), q.end()), q.end());

for (ll i = 1; i <= p; i++) val[i] = lower_bound(q.begin(), q.end(), val[i]) - q.begin() + 1;

dfs(1, 0);

for (ll i = 1; i <= num; i++)

for (ll i = 1; i <= p; i++)

for (ll i = p; i; i--) st[vblock[i]] = i;

for (ll x, y, i = 1; i <= q; i++)

sort(a+1, a+q+1);

ll l = 1, r = 0;

for (ll i = 1; i <= q; i++)

for (ll i = 1; i <= q; i++) printf("%lld\n", ans[i]);

return 0;

}ll gtn(ll kth)

}for (ll i = lv; i <= rv; i++)

return -1;

}void calc(ll pos)

} else

}used[pos] ^= 1;

}void dfs(ll n, ll ff)

}out[n] = ++num, seq[num] = n;

}ll lca(ll x, ll y)

void add(ll x, ll y) ; head[x] = cnt;}

P3242 HNOI2015 接水果

題面 將樹上的路徑包含問題通過dfs序轉換為雙關鍵字區間包含問題, 進而轉換為區間覆蓋類問題。 由此,我們可以通過二分得出每一個詢問的答案。 由於有多次詢問,故只需要整體二分即可。 1 include2 using namespace std 3int n p q x y z 4int head 1...

Luogu3242 HNOI2015 接水果

luogu 我今天做兩道整體二分結果全都是bzoj許可權題??? 我們抓住 盤子的路徑是水果的路徑的子路徑 這個條件。 考慮每一個盤子路徑 u v ,討論它可以作為哪些水果路徑的子路徑。 如果說 u v 不是祖孫關係,那麼水果路徑的兩端點就必須分別在以 u 和 v 為根的子樹中。即若一個水果路徑 a ...

HNOI2015 接水果

這道題要求關於第k大的東西,所以可以想到用主席樹或整體二分 我們可以發現,這道題主要的難點就是路徑之間的包含關係,那麼我們分情況討論 1 lca不是兩個端點 令這個盤子的兩個端點為 a b 如果被一個水果完全覆蓋, 那麼,這個水果的兩端分別在 a b 的子樹中 設 pos a 是 a 的 dfs 序...