CF1479D Odd Mineral Resource

題意：

給定一棵樹，每個點有顏色 $c_i$，多次查詢，每次給定 u,v,l,r，你需要給出一個顏色 x，使得 x 滿足：
$x\in [l,r]$
$x在u到v的路徑上出現了奇數次。$
你需要對于每組查詢給出 x，如果一組查詢不存在合法的 x，則輸出 -1。
$n,m\le 3\times 10^5$

題解：

如果有做過這個題P4396 [AHOI2013]作業，那么本題的大體思路就直接出了
對于$x\in [l,r]$部分我們可以用莫隊來做，對于x在u到v路徑上出現了奇數次，我們可以用分塊來做
題目給的是一個數，所以是樹上莫隊，先用dfs序轉化成鏈，可以用樹剖來寫，一邊求dfs序還求了lca(求lca是樹上莫隊要用的)
復雜度O(nsqrt(n))
好想不好寫，還是我代碼能力太差了
樹上莫隊
樹剖求lca

代碼：

#include <bits/stdc++.h> #include <unordered_map> #define debug(a, b) printf("%s = %d\n", a, b); using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> PII; clock_t startTime, endTime; //Fe~Jozky const ll INF_ll= 1e18; const int INF_int= 0x3f3f3f3f; void read(){}; template <typename _Tp, typename... _Tps> void read(_Tp& x, _Tps&... Ar) {x= 0;char c= getchar();bool flag= 0;while (c < '0' || c > '9')flag|= (c == '-'), c= getchar();while (c >= '0' && c <= '9')x= (x << 3) + (x << 1) + (c ^ 48), c= getchar();if (flag)x= -x;read(Ar...); } template <typename T> inline void write(T x) {if (x < 0) {x= ~(x - 1);putchar('-');}if (x > 9)write(x / 10);putchar(x % 10 + '0'); } void rd_test() { #ifdef ONLINE_JUDGE #elsestartTime = clock ();freopen("data.in", "r", stdin); #endif } void Time_test() { #ifdef ONLINE_JUDGE #elseendTime= clock();printf("\nRun Time:%lfs\n", (double)(endTime - startTime) / CLOCKS_PER_SEC); #endif } const int MAXN= 3e5 + 5; int n, m,cnt_n, Eular[MAXN << 1]; int a[MAXN], Block, Num_Block; int dep[MAXN], ys[MAXN << 1], val[MAXN], sum[MAXN], in[MAXN]; int out[MAXN], ans[MAXN], book[MAXN]; struct Query {int x, y, l, r, id, lca; } q[MAXN]; bool cmp(const Query& in, const Query& sec) {return (ys[in.x] ^ ys[sec.x]) ? (in.x < sec.x) : ((ys[in.x] & 1) ? (in.y < sec.y) : (in.y > sec.y)); } //--樹剖部分 vector<int>vec[MAXN]; int siz[MAXN]; int dfn[MAXN]; int f[MAXN]; int son[MAXN]; int top[MAXN]; void dfs_getson(int u,int fa){siz[u]=1;Eular[++cnt_n]=u;in[u]=cnt_n;for(auto v:vec[u]){if(v==fa)continue;dep[v]=dep[u]+1;f[v]=u;dfs_getson(v,u);siz[u]+=siz[v];if(siz[v]>siz[son[u]])son[u]=v;}Eular[++cnt_n]=u;out[u]=cnt_n; } void dfs_dfn(int u,int fa){top[u]=fa;if(son[u]){dfs_dfn(son[u],fa);}for(auto v:vec [u]){if(v==f[u])continue;if(v!=son[u])dfs_dfn(v,v);} } int LCA(int x,int y){while(top[x]!=top[y]){if(dep[top[x]]>dep[top[y]])swap(x,y);y=f[top[y]];}if(dep[x]>dep[y])swap(x,y);return x; } //-- void Add(int x) {++val[a[x]];if (val[a[x]] & 1)++sum[(a[x] - 1) / Num_Block + 1];else--sum[(a[x] - 1) / Num_Block + 1]; }void Del(int x) {--val[a[x]];if (val[a[x]] & 1)++sum[(a[x] - 1) / Num_Block + 1];else--sum[(a[x] - 1) / Num_Block + 1]; }void Work(int x) {book[x] ? Del(x) : Add(x);book[x]^= 1; }int Ask(int l, int r) {int yl= (l - 1) / Num_Block + 1, yr= (r - 1) / Num_Block + 1;if (yl == yr) {for (int i= l; i <= r; ++i)if (val[i] & 1)return i;return -1;}int el= yl * Num_Block, br= (yr - 1) * Num_Block + 1;for (int i= l; i <= el; ++i)if (val[i] & 1)return i;for (int i= br; i <= r; ++i)if (val[i] & 1)return i;for (int i= yl + 1; i <= yr - 1; ++i) {if (sum[i]) {l= (i - 1) * Num_Block + 1, r= i * Num_Block;for (int j= l; j <= r; ++j)if (val[j] & 1)return j;}}return -1; }int main() {rd_test();read(n,m);for (int i= 1; i <= n; ++i)read(a[i]);for (int i= 1; i < n; ++i) {int x,y;read(x,y);vec[x].push_back(y);vec[y].push_back(x);}dfs_getson(1,1);dfs_dfn(1,1);Block= cnt_n / sqrt(m);Num_Block= sqrt(n);for (int i= 1; i <= cnt_n; ++i)ys[i]= (i - 1) / Block + 1;for (int i= 1; i <= m; ++i) {read(q[i].x,q[i].y,q[i].l,q[i].r);q[i].id= i;q[i].lca= LCA(q[i].x, q[i].y); // cout<<"lca="<<q[i].lca<<endl;if (in[q[i].x] > in[q[i].y])swap(q[i].x, q[i].y);if (q[i].x == q[i].lca) {q[i].x= in[q[i].x];q[i].y= in[q[i].y];q[i].lca= 0;}else {q[i].x= out[q[i].x];q[i].y= in[q[i].y];}}sort(q + 1, q + m + 1, cmp);int l= 1, r= 0;for (int i= 1; i <= m; ++i) {while (l > q[i].x)Work(Eular[--l]);while (r < q[i].y)Work(Eular[++r]);while (l < q[i].x)Work(Eular[l++]);while (r > q[i].y)Work(Eular[r--]);if (q[i].lca)Work(q[i].lca);ans[q[i].id]= Ask(q[i].l, q[i].r);if (q[i].lca)Work(q[i].lca);}for (int i= 1; i <= m; ++i)printf("%d\n", ans[i]);return 0; }

總結

以上是生活随笔為你收集整理的CF1479D Odd Mineral Resource的全部內容，希望文章能夠幫你解決所遇到的問題。

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