宝塔网站搭建教程,导航网站制作,新农村建设网站,云南档案馆网站建设资金CF1479D Odd Mineral Resource
题意#xff1a;
给定一棵树#xff0c;每个点有颜色 cic_ici#xff0c;多次查询#xff0c;每次给定 u,v,l,r#xff0c;你需要给出一个颜色 x#xff0c;使得 x 满足#xff1a; x∈[l,r]x\in [l,r]x∈[l,r] x在u到v的路径上出现了…CF1479D Odd Mineral Resource
题意
给定一棵树每个点有颜色 cic_ici多次查询每次给定 u,v,l,r你需要给出一个颜色 x使得 x 满足 x∈[l,r]x\in [l,r]x∈[l,r] x在u到v的路径上出现了奇数次。x 在 u 到 v 的路径上出现了奇数次。x在u到v的路径上出现了奇数次。 你需要对于每组查询给出 x如果一组查询不存在合法的 x则输出 -1。 n,m≤3×105n,m\le 3\times 10^5n,m≤3×105
题解
如果有做过这个题P4396 [AHOI2013]作业那么本题的大体思路就直接出了 对于x∈[l,r]x\in[l,r]x∈[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 pairint, 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));
}
//--树剖部分
vectorintvec[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(vfa)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(vf[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);yf[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);
// coutlcaq[i].lcaendl;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;
}
