CF1479D Odd Mineral Resource 树上莫队 值域分块

· · 题解

考虑在序列上我们怎么做：

考虑莫队去维护一个值域分块，该值域分块每块维护出现次数为奇数的数的个数，对于每个整块查一下其出现次数为奇数的数的个数，如果不为 0 则遍历该块内的元素，找到合法的 x 直接输出。 并且这个值域分块我们可以做到 O(1) 修改 O(\sqrt{N}) 查询，因此总的复杂度即 O(M\sqrt{N} + N\sqrt{M})。

直接将上面做法上树即可。

卡常小技巧（雾）：只离散化点权并在此基础上建立值域分块，每个询问二分对应区间。

#include <bits/stdc++.h>

namespace wxy{

const int N = 3e5+5,Q = 3e5+5;

int head[N],edge[N<<1],fail[N<<1],tot;

int w[N],b[N<<2],a[N<<1],c[N<<2],n,m,q,dfn,S;

int ans[Q],f[25][N],d[N],st[N],ed[N],use[N<<2],bm[N],cnt[N<<2],cj[N];

bool vis[N];

struct node{int u,v,l,r,LCA,idx;}ask[Q],qa[Q];

inline int read(){
    int s=0,f=1;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) s=s*10+ch-'0',ch=getchar();
    return s*f;
}

inline int get(int x){return std::lower_bound(b + 1,b + 1 + m,x) - b;}

inline bool cmp(node a,node b){return (a.v/1001)==(b.v/1001)?a.u<b.u:a.v<b.v;}

inline void ins(int x,int y){
    edge[++tot] = y;
    fail[tot] = head[x];
    head[x] = tot;
}

inline void dfs(int x){
    vis[x] = true; st[x] = ++dfn; a[dfn] = x;
    for (int i = 1; i <= 19; i++)
        f[i][x] = f[i-1][f[i-1][x]];
    for (int i = head[x]; i; i = fail[i]){
        int v = edge[i];
        if (vis[v]) continue;
        d[v] = d[x] + 1; f[0][v] = x;
        dfs(v);
    }
    ed[x] = ++dfn; a[dfn] = x;
}

inline int lca(int x,int y){
    if (d[x] < d[y]) std::swap(x,y);
    for (int i = 19; i >= 0; i--)
        if (d[f[i][x]] >= d[y]) x = f[i][x];
    if (x == y) return x;
    for (int i = 19; i >= 0; i--)
        if (f[i][x] != f[i][y]) {x = f[i][x]; y = f[i][y];}
    return f[0][x];
}

inline int getL(int idx){return (idx-1)*S+1;}
inline int getR(int idx){return std::min(idx*S,m);}

inline void init(){for (int i = 1; i <= m; i++) bm[i] = (i-1)/S+1;}

inline int bf(int l,int r){
    for (int i = l; i <= r; i++)
        if (cnt[i] % 2 == 1) return b[i];
    return -1;
}

inline int query(int l,int r){
    if (bm[l] == bm[r]) return bf(l,r);
    for (int i = l; i <= getR(bm[l]); i++){
        if (cnt[i] % 2 == 1) return b[i];
    }
    for (int i = getL(bm[r]); i <= r; i++){
        if (cnt[i] % 2 == 1) return b[i];
    }
    for (int i = bm[l] + 1; i < bm[r]; i++)
        if (cj[i] > 0) return bf(getL(i),getR(i));
    return -1;
}

inline void change(int x,int v){cnt[x] += v;cnt[x]%2==0?cj[bm[x]]--:cj[bm[x]]++;}

inline void add(int x){change(x,1);}
inline void del(int x){change(x,-1);}

inline void Add(int x){use[x] ? del(w[x]) : add(w[x]); use[x] ^= 1;}

inline void solve(){
    init();int l = 1,r = 0; //std::cout << q;
    for (int i = 1; i <= q; i++){
        int ql = qa[i].u,qr = qa[i].v;
        int qL = qa[i].l,qR = qa[i].r; 
        //std::cout << qL << " " << qR << std::endl;
        while (l < ql){Add(a[l]); l++;}
        while (l > ql){l--; Add(a[l]);}
        while (r < qr){r++; Add(a[r]);}
        while (r > qr){Add(a[r]); r--;}
        if (qa[i].l == qa[i].r && qa[i].l == 0) {ans[qa[i].idx] = -1; continue;}
        if (qa[i].LCA != -1) Add(qa[i].LCA);
        ans[qa[i].idx] = query(qL,qR);
        if (qa[i].LCA != -1) Add(qa[i].LCA);
    }
}

inline void fprint(){for (int i = 1; i <= q; i++) printf("%d\n",ans[i]);}

inline void initlr(){
    for (int i = 1; i <= q; i++){
        int l = ask[i].l,r = ask[i].r;
        int pl = get(l),pr = get(r);
        if (pr > m) pr--;
        if (pl > m) pl--;
        if (b[pl] > r) {ask[i].l = ask[i].r = 0; continue;}
        if (b[pr] > r) pr--;
        if (b[pr] < l) {ask[i].l = ask[i].r = 0; continue;}
        ask[i].l = pl; ask[i].r = pr;
    }
}

inline void main(){
    #ifndef ONLINE_JUDGE
        freopen("in.in","r",stdin);
        freopen("out.out","w",stdout);
    #endif
    dfn = m = tot = 0; memset(d,-1,sizeof d);
    n = read(); q = read(); S = 800;
    for (int i = 1; i <= n; i++) w[i] = read();
    for (int i = 1; i <= n; i++) c[i] = w[i]; int idx = n;
    std::sort(c + 1,c + 1 + idx);
    for (int i = 1; i <= idx; i++)
        if (i == 1 || c[i] != c[i-1]) b[++m] = c[i];
    for (int i = 1; i <= n; i++) w[i] = get(w[i]);
    for (int i = 1; i < n; i++){
        int a,b; a = read(); b = read();
        ins(a,b); ins(b,a);
    }
    d[1] = 0; dfs(1);
    for (int i = 1; i <= q; i++){
        ask[i].u = read(); ask[i].v = read(); 
        ask[i].l = read(); ask[i].r = read();
    }
    initlr();
    for (int i = 1; i <= q; i++){
        if (st[ask[i].u] > st[ask[i].v]) std::swap(ask[i].u,ask[i].v);
        int LCA = lca(ask[i].u,ask[i].v); //ask[i].l = get(ask[i].l); ask[i].r = get(ask[i].r);
        int x = ask[i].u,y = ask[i].v;
        if (LCA == x) {qa[i].u = st[x]; qa[i].v = st[y]; qa[i].LCA = -1;}
        else {qa[i].u = ed[x]; qa[i].v = st[y]; qa[i].LCA = LCA;}
        qa[i].idx = i; qa[i].l = ask[i].l; qa[i].r = ask[i].r;
    }
    std::sort(qa + 1,qa + 1 + q,cmp);
    solve(); fprint();
}

}signed main(){wxy::main(); return 0;}