CF 1479D

Created2021-02-14Updated2021-02-14

連結

題意

給一棵nn個點的樹，點ii上有顏色aia_i
給定qq筆詢問，每筆詢問有u,v,l,ru, v, l, r，請輸出其中一個符合以下條件的顏色cc：

  1. l≤c≤rl \leq c \leq r
  2. 顏色cc在uu到vv的路徑上出現奇數次
    若無滿足的顏色輸出-1

(1≤n,q≤3×105)(1 \leq n, q \leq 3 \times 10^5)

解法

首先要在樹上套資結可能會有點麻煩，先來考慮問題是序列的情況吧
做法可以先建持久化線段樹，留下每一個前綴的線段樹版本
這樣一來問題就會變成給定ll，rr，要如何找出一個位置介於ll和rr之間且數值相異
至於這要怎麼做呢？

這裡我是用hash，不確定有沒有其他較好的做法就是了
對於每一個線段樹節點用一個hash值把它對應區間的值串起來
這樣就相當單純了，只要判斷區間的hash值是不是相同，若相同就回傳-1
否則看左子樹和右子樹誰的hash值不同，就往那裏遞迴下去，跑到根就結束
複雜度會是好好的O(logn)\mathcal{O}(logn)，因為線段數最多分成lognlogn個區間，又最多只會遞迴到根一次

解決完序列，接下來解決樹吧，可以直接建出樹壓平序列
這樣一來兩點的路徑會變成樹壓平序列的一段區間 + lca
又因為這一題的操作是xor，所以完全不用考慮序列重複元素的情況，寫起來會漂亮許多
樹壓平這裡就不細講，詳細可以看板中講義，那裡有蠻詳細的介紹

然後這題還有樹上莫隊 + 值域分塊的作法~

code

第一次寫靜置記憶體的持久化線段樹
我用的hash是，每個節點會生出兩個亂數x,yx, y，那hash = (左兒子hash * x + 右兒子hash * y) % mod
然後還是被卡碰撞QQ，最後開了兩個hash才過

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define test(x) cout << "Line(" << __LINE__ << ") " #x << ' ' << x << endl
#define printv(x) {\
	for (auto i : x) cout << i << ' ';\
	cout << endl;\
}
#define pii pair <int, int>
#define pll pair <lli, lli>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
template<typename A, typename B>
ostream& operator << (ostream& o, pair<A, B> a){
    return o << a.X << ' ' << a.Y;
}
template<typename A, typename B>
istream& operator >> (istream& o, pair<A, B> &a){
    return o >> a.X >> a.Y;
}
const int mod = 1e9 + 7, abc = 864197532, N = 300000, logN = 18, M = 2e7;
auto SEED = chrono::steady_clock::now().time_since_epoch().count();
mt19937 rng(SEED);

int rnd() {return uniform_int_distribution<int>(1, 65535)(rng);}

struct Seg {
    static Seg mem[M], *pt;
    int l, r, m, hash1, hash2, x, y;
    Seg* ch[2];
    Seg () = default;
    Seg (int _l, int _r) : l(_l), r(_r), m(l + r >> 1), x(rnd()), y(rnd()) {
        if (r - l > 1) {
            ch[0] = new (pt++) Seg(l, m);
            ch[1] = new (pt++) Seg(m, r);
            pull();
        } else {
            hash1 = hash2 = 0;
        }
    }
    void pull() {
        hash1 = (1ll * ch[0]->hash1 * x + 1ll * ch[1]->hash1 * y) % mod;
        hash2 = (1ll * ch[0]->hash2 * y + 1ll * ch[1]->hash2 * x) % mod;
    }
    Seg* modify(int p, int v) {
        Seg *now = new (pt++) Seg(*this);
        if (r - l == 1) {
            now->hash1 = now->hash2 = v;
        } else {
            now->ch[p >= m] = now->ch[p >= m]->modify(p, v);
            now->pull();
        }
        return now;
    }
    int query(int p) {
        if (r - l == 1) return hash1;
        return ch[p >= m]->query(p);
    }
} Seg::mem[M], *Seg::pt = mem;

vector <int> adj[N];
vector <Seg*> roots;
int in[N], out[N], jump[N][logN], cnt[N], a[N], _t = 0;

void dfs(int v, int pa) {
    in[v] = _t++;
    jump[v][0] = pa;
    cnt[a[v]] ^= 1;
    roots.pb(roots.back()->modify(a[v], cnt[a[v]]));
    cout << endl;
    for (int u : adj[v]) if (u != pa) {
        dfs(u, v);
    }
    out[v] = _t++;
    cnt[a[v]] ^= 1;
    roots.pb(roots.back()->modify(a[v], cnt[a[v]]));
}

void build() {
    for (int i = 0; i < N; ++i) for (int j = 0; j < logN; ++j) jump[i][j] = -1;
    dfs(0, -1);
    for (int j = 1; j < logN; ++j) {
        for (int i = 0; i < N; ++i) {
            int k = jump[i][j - 1];
            if (~k) jump[i][j] = jump[k][j - 1];
        }
    }
}

bool anc(int u, int v) {
    return in[u] <= in[v] && out[u] >= out[v];
}

int lca(int u, int v) {
    if (anc(u, v)) return u;
    if (anc(v, u)) return v;
    for (int i = logN - 1; ~i; --i) {
        int k = jump[u][i];
        if (~k && !anc(k, v)) u = k;
    }
    return jump[u][0];
}

int query(Seg *tl, Seg *tr, int a, int b, int l, int r) {
    int m = l + r >> 1;
    if (a <= l && r <= b) {
        if (tl->hash1 == tr->hash1 && tl->hash2 == tr->hash2) return -1;
        if (r - l == 1) return l;
        if (tl->ch[0]->hash1 == tr->ch[0]->hash1 && tl->ch[0]->hash2 == tr->ch[0]->hash2) {
            return query(tl->ch[1], tr->ch[1], a, b, m, r);
        }
        return query(tl->ch[0], tr->ch[0], a, b, l, m);
    } else {
        if (a < m) {
            int res = query(tl->ch[0], tr->ch[0], a, b, l, m);
            if (res != -1) return res;
        }
        if (m < b) {
            int res = query(tl->ch[1], tr->ch[1], a, b, m, r);
            if (res != -1) return res;
        }
        return -1;
    }
}

int main () {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, q, u, v, l, r;
    cin >> n >> q;
    for (int i = 0; i < n; ++i) cin >> a[i], --a[i];
    for (int i = 0, u, v; i < n - 1; ++i) {
        cin >> u >> v, --u, --v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    roots.pb(new (Seg::pt++) Seg(0, n));
    build();
    while (q--) {
        cin >> u >> v >> l >> r, --u, --v, --l;
        int k = lca(u, v);
        Seg *tl, *tr;
        if (k == u) {
            tl = roots[in[u]], tr = roots[in[v] + 1];
        } else if (k == v) {
            tl = roots[in[v]], tr = roots[in[u] + 1];
        } else {
            if (in[u] > in[v]) swap(u, v);
            int t = roots[in[v] + 1]->query(a[k]);
            tl = roots[out[u]], tr = roots[in[v] + 1]->modify(a[k], t ^ 1);
        }
        int ans = query(tl, tr, l, r, 0, n);
        cout << (~ans ? ans + 1 : -1) << '\n';
    }
}