字典树笔记

Trie，即字典树，是一个非常强大的数据结构，可以高效处理字符串、异或最大值以及数集维护问题，而且常数非常小。

下面的题可用用 Trie 树实现，主要分为4个等级。

Level 1

Trie 树基础

A 于是他错误的点名开始了

Description

P2580 于是他错误的点名开始了

Solution

首先把给出的 $n$ 个字符串插入 $trie$ 树中。之后询问时，如果给出的字符串在 $trie$ 树中不存在，否则在字符串末尾对应节点打上标记，如果这个点之前已经被打过标记，说明这个字符串在之前已经被询问过了。

Code

于是他错误的点名开始了

#include <bits/stdc++.h>

using namespace std;

struct trie {
    trie *son[26];
    trie() {
        for (int i = 0; i < 26; i++) son[i] = NULL;
        tag = 0;
    }
    bool tag;
};

trie *root = new trie;
int n, m;
string s;

void insert(const string &s) {
    trie *cur = root;
    for (int i = 0; i < s.size(); i++) {
        int temp = s[i] - 'a';
        if (cur->son[temp] == NULL) cur->son[temp] = new trie;
        cur = cur->son[temp];
    }
}

int search(const string &s) {
    trie *cur = root;
    for (int i = 0; i < s.size(); i++) {
        int temp = s[i] - 'a';
        if (cur->son[temp] == NULL) return 0;
        cur = cur->son[temp];
        if (i == s.size() - 1) {
            if (!cur->tag)
                return cur->tag = 1, 1;
            else
                return 2;
        }
    }
}

int main() {
    cin >> n;
    while (n--) cin >> s, insert(s);
    cin >> m;
    while (m--) {
        cin >> s;
        int now = search(s);
        if (now == 0)
            cout << "WRONG" << endl;
        else if (now == 1)
            cout << "OK" << endl;
        else
            cout << "REPEAT" << endl;
    }
    return 0;
}

B PHONELST Phone List

Description

SP4033 PHONELST - Phone List

Solution

考虑两种情况，若当前串是前面已插入的串中某一个串的前缀，那么它在 $ trie$ 上对应的最后一个节点之前应该被访问过；若前面已插入的串中存在当前串的前缀，那么在插入当前串时，一定会访问到 $trie$ 上的某个节点，且该节点对应之前某个串的结尾。因此只需要打两个标记，一个记录节点是否被访问过，一个记录节点是否对应某个串的结尾，这两个标记边插入边更新即可。

Code

#include <bits/stdc++.h>

using namespace std;

struct trie {
    trie *son[10];
    trie() {
        for (int i = 0; i < 10; i++) son[i] = NULL;
        visTag = isEnd = 0;
    }
    bool visTag, isEnd;
} * root;

int n, T;
bool ans;
string s;

void insert(const string &s) {
    trie *cur = root;
    for (int i = 0; i < s.size(); i++) {
        int temp = s[i] - '0';
        if (cur->son[temp] == NULL) cur->son[temp] = new trie;
        cur = cur->son[temp];
        if (cur->isEnd) {
            ans = 0;
            break;
        }
        if (i == s.size() - 1) {
            cur->isEnd = 1;
            if (cur->visTag) ans = 0;
        }
        cur->visTag = 1;
    }
}

void trie_delete(trie *cur) {
    for (int i = 0; i < 10; i++)
        if (cur->son[i]) trie_delete(cur->son[i]);
    delete cur;
}

int main() {
    cin >> T;
    while (T--) {
        root = new trie;
        ans = 1;
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> s, insert(s);
        puts(ans ? "YES" : "NO");
        trie_delete(root);
    }
    return 0;
}

Level 2

$01Trie$ 贪心计算最大异或值

A Xor Sum

Description

HDU 4825 - Xor Sum

Solution

首先将集合中的每个数化为二进制形式，分别从高位到低位依次插入 $trie$ 树中。对于任意给定的数，要使异或结果最大，那么异或结果的每一位尽可能是1，也就是说给定的数，和使异或结果最大的数，在每一位的值尽可能相反。每次贪心的选取，在 $trie$ 树上走互补的链即可。单次查询的复杂度为
$log_2(S)$。

注：用指针版 $trie$ 树直接 $new$ 的话常数较大，会被卡。可以自己手写$newNode$ 函数，或者改用数组版。

Code

Xor Sum

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int BIT = 32;

struct trie {
    int son[2];
    trie() { son[0] = son[1] = -1; }
} trie[16000000];

int root = 0;
int n, m;

ll read() {
    char ch = getchar();
    ll x = 0, f = 1;
    while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : 1), ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
    return x * f;
}

void insert(ll val) {
    static int tot;
    int cur = root;
    for (int i = BIT; ~i; i--) {
        int now = (val >> i) & 1;
        if (trie[cur].son[now] == -1) trie[cur].son[now] = ++tot;
        cur = trie[cur].son[now];
    }
}

void query(ll val) {
    int cur = root;
    ll ans = 0;
    for (int i = BIT; ~i; i--) {
        ll now = (val >> i) & 1;
        if (trie[cur].son[now ^ 1] != -1)
            ans |= (now ^ 1) << i, cur = trie[cur].son[now ^ 1];
        else
            ans |= now << i, cur = trie[cur].son[now];
    }
    printf("%lld\n", ans);
}

int main() {
    n = read(), m = read();
    for (int i = 1; i <= n; i++) insert(read());
    for (int i = 1; i <= m; i++) query(read());
    return 0;
}

B Chip Factory

Description

HDU 5536 - Chip Factory

Solution

做法和上一道类似。先把给出的 $n$ 个数插入 $trie$ 树，然后枚举 $i$ 和 $j$，把 $s[i] + s[j]$ 放到 $trie$ 树上贪心地查询即可,单次查询复杂度为 $log_2(s)$。需要注意的是，题目要求 $i,j,k$ 互不相同，因此选了 $s[i],s[j]$ 后，应将它们从 $trie$ 树上删除。具体的，每个节点记一个 $cnt$， 删除的时候让 $cnt-1$ ，查询时如果该节点 $cnt$ 为 0 说明已被删除，则不能选这个节点。单次查询结束后再把 $s[i],s[j]$ 插入 $trie$ 树即可，这样不影响之后的查询。

Code

Chip Factory

#include <bits/stdc++.h>

using namespace std;

int n, a[1001], mx = 0;
const int BIT = 31;

struct trie {
    int son[2];
    int cnt;
    trie() {
        son[0] = son[1] = -1;
        cnt = 0;
    }
} trie[1001 * (BIT + 1)];
int root = 0;

int read() {
    char ch = getchar();
    int x = 0, f = 1;
    while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : 1), ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
    return x * f;
}

void insert(int val) {
    static int tot;
    int cur = root;
    for (int i = BIT; ~i; i--) {
        int now = (val >> i) & 1;
        if (trie[cur].son[now] == -1) trie[cur].son[now] = ++tot;
        cur = trie[cur].son[now];
        trie[cur].cnt++;
    }
}

void trie_delete(int val) {
    int cur = root;
    for (int i = BIT; ~i; i--) {
        int now = (val >> i) & 1;
        cur = trie[cur].son[now];
        trie[cur].cnt--;
    }
}

void trie_add(int val) {
    int cur = root;
    for (int i = BIT; ~i; i--) {
        int now = (val >> i) & 1;
        cur = trie[cur].son[now];
        trie[cur].cnt++;
    }
}

void query(int val, int x, int y) {
    trie_delete(a[x]), trie_delete(a[y]);
    int cur = root;
    int ans = 0;
    for (int i = BIT; ~i; i--) {
        int now = (val >> i) & 1;
        if (trie[cur].son[now ^ 1] != -1 && trie[trie[cur].son[now ^ 1]].cnt)
            ans |= 1 << i, cur = trie[cur].son[now ^ 1];
        else if (trie[trie[cur].son[now]].cnt)
            cur = trie[cur].son[now];
        else
            return;
    }
    trie_add(a[x]), trie_add(a[y]);
    mx = max(mx, ans);
}

int main() {
    n = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    for (int i = 1; i <= n; i++) insert(a[i]);
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++) query(a[i] + a[j], i, j);
    cout << mx;
    return 0;
}

C Nikitosh and xor

Description

Codechef REBXOR - Nikitosh and xor

Solution

记 $preMx[i]$ 表示从 $1$ 到 $i$ 的最大连续片段异或和，$posMx[i]$ 表示从 $i$ 到 $n$ 的最大连续片段异或和。显然，答案为 $\max\limits_{0<i<n}(preMx[i]+posMx[i+1])$。接下来只需要预处理出 $preMx[i]$ 和 $posMx[i]$ 即可。
记 $preXor[i]$ 表示 $1$ 到 $i$ 的前缀异或和。同时设 $preXor[k](0<=k <i)$ 已计算出，并且已被插入 $trie$ 中, 那么根据异或运算的性质，有 $preMx[i]=\max\limits_{0<=k<i}(preMx[i-1], preXor[i]⊕preXor[k])$，而$\max\limits_{0<=k<i}(preXor[i]⊕preXor[k])$ 可以在 $trie$ 树上，在 $log_2(a)$的时间内贪心地求出。同样的，容易求出 $posMx[i]$。

Code

Nikitosh and xor

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int BIT = 31;
const int maxn = 400005;
int n, a[maxn], tot;
ll preXor = 0, posXor = 0, preMx[maxn], posMx[maxn];
ll ans = 0;

struct trie {
    int son[2];
    trie() { son[0] = son[1] = -1; }
} trie[maxn * BIT * 2];
int root;

int read() {
    char ch = getchar();
    int x = 0, f = 1;
    while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : 1), ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
    return x * f;
}

void insert(ll val) {
    int cur = root;
    for (int i = BIT; ~i; i--) {
        int now = (val >> i) & 1;
        if (trie[cur].son[now] == -1) trie[cur].son[now] = ++tot;
        cur = trie[cur].son[now];
    }
}

ll query(ll val) {
    int cur = root;
    ll ans = 0;
    for (int i = BIT; ~i; i--) {
        int now = (val >> i) & 1;
        if (trie[cur].son[now ^ 1] != -1)
            ans |= 1ll << i, cur = trie[cur].son[now ^ 1];
        else
            cur = trie[cur].son[now];
    }
    return ans;
}

int main() {
    n = read();
    for (int i = 1; i <= n; i++) a[i] = read();

    insert(0);
    for (int i = 1; i <= n; i++) {
        preXor ^= a[i];
        insert(preXor);
        preMx[i] = max(preMx[i - 1], query(preXor));
    }
    for (int i = 0; i <= tot; i++) trie[i].son[0] = trie[i].son[1] = -1;
    tot = 0;

    insert(0);
    for (int i = n; i >= 1; i--) {
        posXor ^= a[i];
        insert(posXor);
        posMx[i] = max(posMx[i + 1], query(posXor));
    }
    for (int i = 1; i <= n - 1; i++) ans = max(ans, posMx[i + 1] + preMx[i]);
    cout << ans;
    return 0;
}

D 最长异或路径

Descritiption

P4551 最长异或路径

Solution

首先 $dfs$ 求出每个点 $i$ 到根节点路径上的异或和，记为 Xor[i]。显然，答案为 $\max\limits_{1<=u<=n}( \max\limits_{1<=v<=n}(Xor[u]⊕Xor[v]))$。对于任意节点 $u$，它和其它节点的最大异或值可以在 $trie$ 树上在 $log_2(w)$ 的时间内贪心地求得。

Code

最长异或路径

#include <bits/stdc++.h>

using namespace std;

const int maxn = 100005;
const int BIT = 30;

int p[maxn], XOR[maxn];
int n, u, v, w, ans;
bool vis[maxn];

struct trie {
    trie *son[2];
    int val;
    trie() { son[0] = son[1] = NULL; }
} * root;

struct edge {
    int nxt, to, val;
} e[maxn * 2];

template <class T>
void read(T &x, int f = 1) {
    char ch = getchar();
    x = 0;
    while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : 1), ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
    x *= f;
}

void add(int from, int to, int val) {
    static int t;
    e[t].to = to, e[t].val = val, e[t].nxt = p[from], p[from] = t++;
}

void dfs(int now, int val) {
    XOR[now] = val, vis[now] = 1;
    for (int i = p[now]; ~i; i = e[i].nxt) {
        int to = e[i].to;
        if (!vis[to]) dfs(to, val ^ e[i].val);
    }
}

void insert(int val) {
    trie *cur = root;
    for (int i = BIT; ~i; i--) {
        int now = (val >> i) & 1;
        if (cur->son[now] == NULL) cur->son[now] = new trie;
        cur = cur->son[now];
    }
}

int query(int val) {
    trie *cur = root;
    int ans = 0;
    for (int i = BIT; ~i; i--) {
        int now = (val >> i) & 1;
        if (cur->son[now ^ 1] != NULL)
            ans |= 1 << i, cur = cur->son[now ^ 1];
        else
            cur = cur->son[now];
    }
    return ans;
}

int main() {
    memset(p, -1, sizeof(p));
    read(n);
    for (int i = 1; i <= n - 1; i++) {
        read(u), read(v), read(w);
        add(u, v, w), add(v, u, w);
    }
    dfs(1, 0);
    root = new trie;
    for (int i = 1; i <= n; i++) insert(XOR[i]);
    for (int i = 1; i <= n; i++) ans = max(ans, query(XOR[i]));
    cout << ans;
    return 0;
}

Level 3

Trie 树 应用

A USACO08DEC Secret Message G

Descritption

P2922 USACO08DEC Secret Message G

Solution

首先按题意建好 $trie$ 树。对于一个暗号，需要求出有多少条信息是它的前缀，以及它是多少条信息的前缀。用 $cntEnd$ 表示有多少条信息以该节点为结尾，$sum$ 表示该节点对应信息是多少条信息的前缀。每次查询可以求出在最后一位之前该暗号前缀的个数，在最后一个节点通过 $sum$ 可以得到这个暗号是多少条信息的前缀，加起来去个重即可。

Code

Secret Message G

#include <bits/stdc++.h>

using namespace std;

int m, n, k;
bool v;

struct trie {
    trie* son[2];
    int cntEnd, sum;
    trie() {
        son[1] = son[0] = NULL;
        cntEnd = sum = 0;
    }
} * root;

template <class T>
void read(T& x, int f = 1) {
    char ch = getchar();
    x = 0;
    while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : 1), ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
    x *= f;
}

void insert(vector<bool>& bin) {
    trie* cur = root;
    for (int i = 0; i < bin.size(); i++) {
        int now = bin[i];
        if (cur->son[now] == NULL) cur->son[now] = new trie;
        cur = cur->son[now];
        cur->sum++;
    }
    cur->cntEnd++;
}

int query(vector<bool>& bin) {
    trie* cur = root;
    int ans = 0;
    for (int i = 0; i < bin.size(); i++) {
        int now = bin[i];
        if (cur->son[now] == NULL) return ans;
        cur = cur->son[now];
        ans += cur->cntEnd;
    }
    ans += cur->sum - cur->cntEnd;
    return ans;
}

int main() {
    read(m), read(n);
    root = new trie;
    for (int i = 1; i <= m; i++) {
        read(k);
        vector<bool> bin;
        for (int i = 1; i <= k; i++) read(v), bin.push_back(v);
        insert(bin);
    }
    for (int i = 1; i <= n; i++) {
        read(k);
        vector<bool> bin;
        for (int i = 1; i <= k; i++) read(v), bin.push_back(v);
        cout << query(bin) << endl;
    }
    return 0;
}

B IOI2008 Type Printer 打印机

Descritption

P4683 IOI2008 Type Printer 打印机

Solution

容易发现，所有字符串都要打印，除了最后一个外都要删除。要使按键次数最少，最后打印的字符串必须最长。对最长的字符串在 $trie$ 树上打个标记，$dfs$ 时把有标记的节点放在最后搜索就行了。

Code

Type Printer

#include <bits/stdc++.h>

using namespace std;

int n;
char s[21];
vector<char> ans;
struct trie {
    int son[26];
    bool isEnd, tag;
    trie() {
        for (int i = 0; i < 26; i++) son[i] = -1;
        isEnd = tag = 0;
    }
} trie[25000 * 20];
int root, tot;

void insert(const string& s) {
    int cur = root;
    for (int i = 0; i < s.size(); i++) {
        int now = s[i] - 'a';
        if (trie[cur].son[now] == -1) trie[cur].son[now] = ++tot;
        cur = trie[cur].son[now];
    }
    trie[cur].isEnd = 1;
}

void addTag(const string& s) {
    int cur = root;
    for (int i = 0; i < s.size(); i++) {
        cur = trie[cur].son[s[i] - 'a'];
        trie[cur].tag = 1;
    }
}

void dfs(int now) {
    int last = -1;
    for (int i = 0; i < 26; i++) {
        if (trie[now].son[i] != -1) {
            if (!trie[trie[now].son[i]].tag) {
                ans.push_back(i + 'a');
                if (trie[trie[now].son[i]].isEnd) ans.push_back('P');
                dfs(trie[now].son[i]);
                ans.push_back('-');
            } else
                last = i;
        }
    }
    if (last != -1) {
        ans.push_back(last + 'a');
        if (trie[trie[now].son[last]].isEnd) ans.push_back('P');
        dfs(trie[now].son[last]);
    }
}

int main() {
    scanf("%d", &n);
    int mxLen = 0;
    string lastString;
    for (int i = 1; i <= n; i++) {
        scanf("%s", s);
        if (strlen(s) > mxLen) mxLen = strlen(s), lastString = s;
        insert(s);
    }
    addTag(lastString);
    dfs(root);
    printf("%d\n", ans.size());
    for (int i = 0; i < ans.size(); i++) putchar(ans[i]), putchar('\n');
    return 0;
}

C USACO12DEC First! G

Description

P3065 USACO12DEC First! G

Solution

首先建出 $trie$ 树，然后枚举每一个字符串，考察它能否排在第一个。具体的，将一个字符串放在 $trie$ 树上查询，如果途径某个点，这个点是其它串的结尾，那么该串不可能排第一；否则可以根据节点访问顺序建立关于字母优先级的图，用拓扑排序判断是否存在环，若存在环说明该字符串不能排在第一个。

Code

USACO12DEC First! G

#include <bits/stdc++.h>

using namespace std;

const int maxn = 30005;
int n, ans;
string s[maxn];
int inDegree[26];
vector<int> v[26];
vector<int> firstId;

struct trie {
    trie* son[26];
    bool isEnd;
    trie() {
        for (int i = 0; i < 26; i++) son[i] = NULL;
        isEnd = 0;
    }
} * root;

void insert(const string& s) {
    trie* cur = root;
    for (int i = 0; i < s.size(); i++) {
        if (cur->son[s[i] - 'a'] == NULL) cur->son[s[i] - 'a'] = new trie;
        if (i == s.size() - 1) cur->son[s[i] - 'a']->isEnd = 1;
        cur = cur->son[s[i] - 'a'];
    }
}

bool check(const string& s) {
    for (int i = 0; i < 26; i++) {
        v[i].clear();
        inDegree[i] = 0;
    }
    trie* cur = root;
    for (int i = 0; i < s.size(); i++) {
        for (int j = 0; j < 26; j++)
            if (cur->son[j] != NULL && j != s[i] - 'a') {
                v[s[i] - 'a'].push_back(j);
                inDegree[j]++;
            }
        if (i != s.size() - 1 && cur->son[s[i] - 'a']->isEnd) return false;
        cur = cur->son[s[i] - 'a'];
    }
    stack<int> st;
    for (int i = 0; i < 26; i++)
        if (!inDegree[i]) st.push(i);
    while (!st.empty()) {
        int now = st.top();
        st.pop();
        for (int i = 0; i < v[now].size(); i++) {
            inDegree[v[now][i]]--;
            if (!inDegree[v[now][i]]) st.push(v[now][i]);
        }
    }
    for (int i = 0; i < 26; i++)
        if (inDegree[i]) return false;
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n;
    root = new trie;
    for (int i = 1; i <= n; i++) cin >> s[i], insert(s[i]);
    for (int i = 1; i <= n; i++)
        if (check(s[i])) firstId.push_back(i), ans++;
    cout << ans << endl;
    for (int i = 0; i < firstId.size(); i++) cout << s[firstId[i]] << endl;
    return 0;
}

D CQOI2016 路由表

Description

P5768 CQOI2016 路由表

Solution

先把IP地址按题目要求转化为二进制插入 $trie$ 树，顺便对最后访问的节点记录 $inTime$ 和 $length$, 分别表示这个 $IP$ 地址被插入的时间和掩码长度。查询时，对于 $inTime$ 在 $a$ 和 $b$ 之间的 $IP$ 地址，记录对应掩码长度, 将这两个信息存入 $Vector$；对于 $inTime$ 在 $a$ 之前的节点，更新掩码长度最大值。最后对 $Vector$ 按照 $IP$ 地址按插入时间排序，然后从前到后扫一遍 $Vector$，同时更新掩码长度最大值，就可以知道该待查询的IP地址的路由表项选择发生了多少次变化。

Code

CQOI2016 路由表

#include <bits/stdc++.h>
#define pii pair<int, int>

using namespace std;

int n, x, cntAdd, len, a, b;
char type;
struct trie {
    trie* son[2];
    int inTime, length;
    trie() {
        son[1] = son[0] = NULL;
        inTime = length = 0;
    }
} * root;

int read() {
    char ch = getchar();
    int x = 0, f = 1;
    while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : 1), ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
    return x * f;
}

void insert(vector<bool>& bin, int l, int id) {
    trie* cur = root;
    for (int i = 0; i < l; i++) {
        int now = bin[i];
        if (cur->son[now] == NULL) cur->son[now] = new trie;
        cur = cur->son[now];
        if (i == l - 1) {
            cur->inTime = id;
            cur->length = l;
        }
    }
}

void query(vector<bool>& bin, int l, int r) {
    trie* cur = root;
    int cnt = 0, mx = 0;
    vector<pii> tmp;
    for (int i = 0; i < bin.size(); i++) {
        int now = bin[i];
        if (cur->son[now] == NULL) break;
        cur = cur->son[now];
        if (cur->inTime >= l && cur->inTime <= r)
            tmp.push_back(make_pair(cur->inTime, cur->length));
        else if (cur->inTime < l)
            mx = max(mx, cur->length);
    }
    sort(tmp.begin(), tmp.end());
    for (int i = 0; i < tmp.size(); i++)
        if (tmp[i].second > mx) mx = tmp[i].second, cnt++;
    printf("%d\n", cnt);
}

int main() {
    n = read();
    root = new trie;
    for (int i = 1; i <= n; i++) {
        type = getchar();
        if (type == 'A') {
            cntAdd++;
            vector<bool> bin;
            for (int i = 1; i <= 4; i++) {
                x = read();
                for (int j = 7; ~j; j--) bin.push_back((x >> j) & 1);
            }
            len = read();
            insert(bin, len, cntAdd);
        } else {
            vector<bool> bin;
            for (int i = 1; i <= 4; i++) {
                x = read();
                for (int j = 7; ~j; j--) bin.push_back((x >> j) & 1);
            }
            a = read(), b = read();
            query(bin, a, b);
        }
    }
    return 0;
}

E JSOI2009 电子字典

Description

P4407 JSOI2009 电子字典

Solution

按照题意直接暴搜即可，注意判重。

Code

JSOI2009

#include <bits/stdc++.h>

using namespace std;

int n, m, ans, tot;
string s;
struct trie {
    trie* son[26];
    int endTag;
    trie() {
        for (int i = 0; i < 26; i++) son[i] = NULL;
        endTag = 0;
    }
} * root;
unordered_map<int, bool> vis;

void insert(const string& s, int id) {
    trie* cur = root;
    for (int i = 0; i < s.size(); i++) {
        if (cur->son[s[i] - 'a'] == NULL) cur->son[s[i] - 'a'] = new trie;
        cur = cur->son[s[i] - 'a'];
    }
    cur->endTag = id;
}

bool isWord(const string& s) {
    trie* cur = root;
    for (int i = 0; i < s.size(); i++) {
        if (cur->son[s[i] - 'a'] == NULL) return false;
        cur = cur->son[s[i] - 'a'];
        if (i == s.size() - 1 && cur->endTag) return true;
    }
    return false;
}

void dfs(trie* now, int i, bool canOpt) {
    if (i == s.size()) {
        if (now->endTag && !vis[now->endTag]) ans++, vis[now->endTag] = 1;
        if (canOpt) {
            for (int k = 0; k < 26; k++)
                if (now->son[k] != NULL && now->son[k]->endTag &&
                    !vis[now->son[k]->endTag])
                    ans++, vis[now->son[k]->endTag] = 1;
        }
        return;
    }
    if (!canOpt && now->son[s[i] - 'a'] == NULL) return;
    if (now->son[s[i] - 'a'] != NULL) dfs(now->son[s[i] - 'a'], i + 1, canOpt);
    if (canOpt) {
        //增加一位
        for (int k = 0; k < 26; k++)
            if (now->son[k] != NULL) dfs(now->son[k], i, 0);
        //删除一位
        dfs(now, i + 1, 0);
        //修改一位
        for (int k = 0; k < 26; k++)
            if (now->son[k] != NULL) dfs(now->son[k], i + 1, 0);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    root = new trie;
    for (int i = 1; i <= n; i++) {
        cin >> s;
        insert(s, i);
    }
    for (int i = 1; i <= m; i++) {
        vis.clear();
        cin >> s;
        if (isWord(s))
            cout << -1 << endl;
        else {
            ans = 0;
            dfs(root, 0, 1);
            cout << ans << endl;
        }
    }
    return 0;
}

F AHOI2005 病毒检测

Description

P2536 AHOI2005 病毒检测

Solution

按照题意建出 $trie$ 树，然后记忆化搜索即可。本题有加强版，需要使用 AC 自动机实现通配符模糊匹配。(写完 AC 自动机博客再把链接贴上)

Code

AHOI2005 病毒检测

#include <bits/stdc++.h>

using namespace std;

const int maxn = 505;
int n, ans, len;
char s[maxn], T[maxn * 2];
int isVirus[maxn], firstId[maxn];
int to[200];
bitset<1001> vis[maxn * maxn];

struct trie {
    trie* son[4];
    int endTag, num;
    trie() {
        for (int i = 0; i < 4; i++) son[i] = NULL;
        endTag = num = 0;
    }
} * root;

void insert(const string& s, const int& id) {
    static int tot;
    trie* cur = root;
    for (int i = 0; i < s.size(); i++) {
        if (cur->son[to[s[i]]] == NULL) cur->son[to[s[i]]] = new trie;
        cur = cur->son[to[s[i]]];
        cur->num = ++tot;
    }
    if (!cur->endTag) cur->endTag = id;
    firstId[id] = cur->endTag;
}

void match(trie* now, int i) {
    if (i == len) {
        isVirus[now->endTag] = 1;
        return;
    }
    if (vis[now->num][i]) return;
    vis[now->num][i] = 1;
    if (T[i] == '*') {
        match(now, i + 1);
        for (int k = 0; k < 4; k++)
            if (now->son[k] != NULL)
                match(now->son[k], i + 1), match(now->son[k], i);
    } else if (T[i] == '?') {
        for (int k = 0; k < 4; k++)
            if (now->son[k] != NULL) match(now->son[k], i + 1);
    } else {
        if (now->son[to[T[i]]] != NULL) match(now->son[to[T[i]]], i + 1);
    }
}

int main() {
    to['A'] = 0, to['T'] = 1, to['C'] = 2, to['G'] = 3;
    scanf("%s%d", T, &n);
    len = strlen(T);
    root = new trie;
    for (int i = 1; i <= n; i++) scanf("%s", s), insert(s, i);
    for (int i = 0; i < maxn * maxn; i++) vis[i].reset();
    match(root, 0);
    for (int i = 1; i <= n; i++)
        if (isVirus[firstId[i]]) ans++;
    printf("%d\n", n - ans);
    return 0;
}

G SCOI2016 背单词

Description

P3294 SCOI2016 背单词

Solution

显然，情形 $3$ 比情形 $1$ 和 $2$ 更优，因为情形 $1$ 和情形 $2$ 不管怎样都会吃大于等于 $x$ 个泡椒。只需要考虑情形 $3$，对于情形 $3$ 我们需要构建一种方案，使得$\sum(x-y)$ 最小。

首先将输入的字符串反转后插入 $trie$ 树中，这样转化为前缀方便处理。
容易发现，除了 $root$ 和 一个串最后一个字符对应节点外，其它节点对答案没有影响，我们根据这些终点节点重新构建 $trie$ 树，将多余的节点删掉。以下图为例：

设有字符串：$CA,GDA,HDA,EA,IFB$

原来的 $trie$ 树:

重新构建的 $trie$ 树:

容易发现，一个节点(对应一个字符串)的贡献取决于它和它父亲被选取的时间差。可以证明，按dfs选取，且先访问size小的子树最优。

先证明按 $dfs$ 序选取一定最优，对于以同一深度的节点为根的一系列子树，在一颗中找一个叶子节点 $j$,在另一颗里找一个根节点 $i$ (当前序列中j所在的子树的根在i之前出现)。需要明确的是，只有这两种节点间才能交换顺序，否则得到序列不满足情形 $3$ 。假设 $j$ 在 $i$ 之前代价最小，尝试将 $j$ 放在 $i$ 的后面。可以发现发现 $i$ 的孩子们和 $i$ 的距离都会加 1，所以总代价会增加，而 $j$ 和 $j$ 的父亲的距离一定也会增加，所以总代价也会增加。

再证明优先选取size小的子树更优。实际上，按照dfs序，第i个选取的子树的根的贡献等于之前选取的子树的size的和，所以size小的应该放在前面。

Code SCOI2016 背单词

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 510005;
int n, sz[maxn], in[maxn];
string s;
ll ans;
vector<int> v[maxn];

struct trie {
    int son[26];
    int tag;
    trie() {
        for (int i = 0; i < 26; i++) son[i] = -1;
        tag = 0;
    }
} trie[maxn];
int root, tot;

void insert(const string &s) {
    int cur = root;
    for (int i = s.size() - 1; ~i; i--) {
        int now = s[i] - 'a';
        if (trie[cur].son[now] == -1) trie[cur].son[now] = ++tot;
        cur = trie[cur].son[now];
        if (!i) trie[cur].tag = 1;
    }
}

void rebuild(int now, int pre) {
    for (int i = 0; i < 26; i++) {
        if (trie[now].son[i] != -1) {
            if (trie[trie[now].son[i]].tag) {
                v[pre].push_back(trie[now].son[i]);
                rebuild(trie[now].son[i], trie[now].son[i]);
            } else
                rebuild(trie[now].son[i], pre);
        }
    }
}

bool cmp(const int &a, const int &b) { return sz[a] < sz[b]; }
void dfs(int now) {
    sz[now] = 1;
    for (int i = 0; i < v[now].size(); i++) {
        dfs(v[now][i]);
        sz[now] += sz[v[now][i]];
    }
    sort(v[now].begin(), v[now].end(), cmp);
}

void dfs2(int now) {
    static int tim;
    in[now] = tim++;
    for (int i = 0; i < v[now].size(); i++) {
        ans += tim - in[now];
        dfs2(v[now][i]);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> s, insert(s);
    rebuild(root, root);
    dfs(root);
    dfs2(root);
    cout << ans;
    return 0;
}

H HAOI2017 供给侧改革

Description

P3732 HAOI2017 供给侧改革

Solution

在线不太好做，考虑离线处理，将询问按右端点排序,从 $1$ 到 $n$ 枚举起始位 $i$，将起始位置 $i$ 到最后一位的部分插入 $trie$ 树中，然后查询对右端点为 $i$ 的询问的答案。实际上，由于数据随机生成，容易推出最长公共前缀长度不超过40，所以只需要从起始位 $i$ 开始往后插入 $40$ 位就可以了。

对任意位置$i$，记 $pos[k]$ 对应最大左端点，使得 $data(pos[k],i)=k$。显然，$k$ 越大，$pos[k]$ 越小。同时 $trie$ 树上每个节点记一个 $last$，表示上次被访问时对应串的起点位置。插入时，容易算出之前的插入的串和当前串
被插入部分的公共前缀的长度 $l$, 并更新 $pos[l]$ = $\max(pos[l],last)$,对应新的最大左端点。

每次插入后，对所有以 $i$ 为右端点的询问，枚举公共前缀的长度 $k$，根据 $pos$ 中的信息即可求得该询问的答案。

Code

HAOI2017 供给侧改革

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 100005;
int n, m, pos[50];
// pos[k]对应最大左端点，使得 data(pos[k],i)=k;
//大于pos[k]的位置，data(pos[k],i)<k
char s[maxn];
ll ans[maxn];
struct trie {
    trie* son[2];
    int last;
    trie() {
        son[0] = son[1] = NULL;
        last = 0;
    }
} * root;

struct Question {
    int l, r, qId;
    bool operator<(const Question& other) { return r < other.r; }
} Q[maxn];

int read() {
    char ch = getchar();
    int x = 0, f = 1;
    while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : 1), ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
    return x * f;
}

void insert(int st) {
    trie* cur = root;
    for (int i = st; i <= min(st + 39, n); i++) {
        int now = s[i] - '0';
        if (cur->son[now] == NULL) cur->son[now] = new trie;
        cur = cur->son[now];
        if (cur->last) pos[i - st + 1] = max(pos[i - st + 1], cur->last);
        cur->last = st;
    }
}

int main() {
    n = read(), m = read();
    scanf("%s", s + 1);
    for (int i = 1; i <= m; i++) Q[i].l = read(), Q[i].r = read(), Q[i].qId = i;
    sort(Q + 1, Q + m + 1);
    root = new trie;
    for (int i = 1, j = 1; i <= n; i++) {
        insert(i); //插入起始位置在i的串
        while (j <= m && Q[j].r == i) {//以i结尾询问
            for (int k = 1; k <= 40; k++) {//枚举长度
                if (pos[k] >= Q[j].l)// pos[k]在[l,r]内
                    ans[Q[j].qId] +=k * (pos[k] - max(pos[k + 1] + 1, Q[j].l) +1); 
                else
                    break;  
                    // data(pos[k+1]+1,pos[k])=k
                    //由pos单调性可知更大的k都不合法
            }
            j++;  //下一个询问
        }
    }
    for (int i = 1; i <= m; i++) printf("%lld\n", ans[i]);
    return 0;
}

I BJOI2016 IP地址

Description

P5460 BJOI2016 IP地址

Solution

一个 $ip$ 地址在操作 $[l+1,r]$ 匹配到的生效规则变化的次数等于 在 $[1,r]$ 的变化次数减去 在$[1,l]$ 的变化次数。容易发现，不论删除还是插入某一规则，在 $trie$ 树中，只会对当前规则的结尾和当前规则结尾往下的第一个结尾之间的全部节点产生影响。

用 $cnt$ 记录到当前节点匹配到的生效规则变化的次数，$lazyTag$作为延迟下放标记，$endTag$ 记录是否为某条规则的结尾。在插入/删除一个规则时，在结尾处更新 $endTag= endTag + type$($type$ 为 1 表示插入，-1 表示删除)，$cnt++$ 表示匹配到的生效规则发生了一次变化，同时更新 $lazyTag$。插入/删除的同时沿途下放标记，直到遇到下一个结尾停止。

将操作按 1 到 $n$ 的顺序进行，对于操作 $i$, 可以预处理出哪些询问的左端点或右端点是 $i$。将这些询问的 IP 地址放在当前的 $trie$ 上查询，同时沿途下放标记, 返回末尾处的 $cnt$ 即可求得该 IP 地址在操作$[1,i]$ 匹配到的生效规则变化的次数。如果是左端点，则这个询问的答案应减去 $cnt$; 否则，这个询问的答案应加上 $cnt$。

Code

BJOI2016 IP地址

#include <bits/stdc++.h>

using namespace std;
const int maxn = 1e5 + 5;

int n, m;
char opt[4];
string principle[maxn], ip[maxn];
int l[maxn], r[maxn], type[maxn], ans[maxn];
vector<int> vl[maxn], vr[maxn];

struct trie {
    trie* son[2];
    int lazyTag, endTag, cnt;
    trie() {
        son[0] = son[1] = NULL;
        lazyTag = endTag = cnt = 0;
    }
} * root;

void pushDown(trie* cur) {
    if (cur->son[0] == NULL) cur->son[0] = new trie;
    if (cur->son[1] == NULL) cur->son[1] = new trie;

    if (!cur->son[0]->endTag)
        cur->son[0]->lazyTag += cur->lazyTag, cur->son[0]->cnt += cur->lazyTag;
    if (!cur->son[1]->endTag)
        cur->son[1]->lazyTag += cur->lazyTag, cur->son[1]->cnt += cur->lazyTag;

    cur->lazyTag = 0;
}

void insert(const string& s, int type) {
    trie* cur = root;
    for (int i = 0; i < s.size(); i++) {
        pushDown(cur);
        cur = cur->son[s[i] - '0'];
    }
    cur->endTag += type;
    cur->lazyTag++;
    cur->cnt++;
}

int query(const string& s) {
    trie* cur = root;
    for (int i = 0; i < s.size(); i++) {
        if (cur->son[s[i] - '0'] == NULL) return cur->cnt;
        pushDown(cur);
        cur = cur->son[s[i] - '0'];
    }
    return cur->cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> opt >> principle[i];
        type[i] = (opt[0] == 'A' ? 1 : -1);
    }
    for (int i = 1; i <= m; i++) {
        cin >> ip[i] >> l[i] >> r[i];
        vl[l[i]].push_back(i);
        vr[r[i]].push_back(i);
    }
    root = new trie;
    for (int i = 1; i <= n; i++) {
        insert(principle[i], type[i]);
        for (int j = 0; j < vl[i].size(); j++) {
            int id = vl[i][j];
            ans[id] -= query(ip[id]);
        }
        for (int j = 0; j < vr[i].size(); j++) {
            int id = vr[i][j];
            ans[id] += query(ip[id]);
        }
    }
    for (int i = 1; i <= m; i++) cout << ans[i] << endl;
    return 0;
}

J Ynoi2011 竞赛实验班

Description

P5312 Ynoi2011 竞赛实验班

Solution

对于操作 1、3，根据异或运算性质, 开一个全局异或值 $X$ ( 初始为0 ）, 每次将 $X$ 异或上操作 3 给出的 $x$。当插入一个数 $x$ 时，将 $x$ 异或上 $X$ 再插入，这样在查询时再异或上当前的 $X$ 就可以得到插入 $x$ 之后，进行一系列操作 3 后 $x$ 的真实值。

注意到经过操作 4， 任意时刻的序列一定是前半段有序，后半段无序的，这两段对应区间记为 $[1,lastN]$ 和 $[lastN+1,n]$。
实际上，构建出的 $trie$ 树某种程度上说本身就是排好序的，所以对于操作 2，有序的部分可以在 $trie$ 上用类似平衡树查询前缀和的方式；无序的部分可以用二维数组记每一位 1 的个数的前缀和求出，这个前缀和在排序后清零。

综合上述分析，查询应分有两种。具体的，对于无序部分的查询，根据 $X$ 的值，结合前缀和数组，可以推出在 $[lastN+1,n]$ 这段区间上每一位 1 的个数的实际值，一位一位累加可得答案；对于有序的部分，应分别求出前 $lastN$ 个数的和以及前 $l-1$ 个数的和，两者相减可得有序部分 $[l,lastN]$ 的和，详见代码。

Code

Ynoi2011 竞赛实验班

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 1e5 + 5;
int n, m, type, l, r, X, lastN, lastXor;
int a[maxn * 2], sum[maxn * 2][31];

struct trie {
    trie* son[2];
    int sz;
    int cnt[31];
    trie() {
        son[0] = son[1] = NULL;
        for (int i = 0; i < 31; i++) cnt[i] = 0;
        sz = 0;
    }
} * root;

int read() {
    char ch = getchar();
    int x = 0, f = 1;
    while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : 1), ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
    return x * f;
}

void insert(const int& x) {
    trie* cur = root;
    for (int i = 30; i >= 0; i--) {
        int to = (x >> i) & 1;
        if (cur->son[to] == NULL) cur->son[to] = new trie;
        cur = cur->son[to];
        cur->sz++;
        for (int k = 0; k <= 30; ++k) cur->cnt[k] += (x >> k) & 1;
    }
}

ll query2(const int& l, const int& r) {
    ll ans = 0, len = r - l + 1;
    for (int i = 0; i < 31; i++) {
        ll cnt = sum[r][i] - sum[l - 1][i];
        if ((X >> i) & 1) cnt = len - cnt;
        ans += cnt << i;
    }
    return ans;
}

ll query1(int sz) {
    if (!sz) return 0;
    ll ans = 0, val = 0; 
    //val 记录排名第sz的数在当前树中的值，最后实际值要异或全局X
    //ans 在查询的时候已经对X异或过了，最后不需要再异或
    trie* cur = root;
    for (int i = 30; i >= 0; --i) {
        int to = (lastXor >> i) & 1;  //最后一次排序后的异或值
        if (cur->son[to] != NULL && sz <= cur->son[to]->sz)
            cur = cur->son[to], val |= to << i;
        else {
            int sizeOfSon = (cur->son[to] == NULL ? 0 : cur->son[to]->sz);
            //统计son[to]的贡献, 注意用的是当前异或值
            for (int k = 0; k < 31; k++) {
                ll cnt = (cur->son[to] == NULL ? 0 : cur->son[to]->cnt[k]);
                if ((X >> k) & 1) cnt = sizeOfSon - cnt;//实际值要异或X
                ans += cnt << k;
            }
            //走另外一边
            sz -= sizeOfSon;
            cur = cur->son[to ^ 1];
            val |= (to ^ 1) << i;
        }
    }
    return ans + (val ^ X) * sz;  //可能多个数结尾在同一链
}

int main() {
    n = read();
    for (int i = 1; i <= n; i++) {
        a[i] = read();
        for (int k = 0; k < 31; k++)
            sum[i][k] = sum[i - 1][k] + ((a[i] >> k) & 1);
    }
    m = read();
    root = new trie;
    for (int i = 1; i <= m; i++) {
        type = read();
        if (type == 1) {
            a[++n] = read() ^ X;
            for (int k = 0; k < 31; k++)
                sum[n][k] = sum[n - 1][k] + ((a[n] >> k) & 1);
        } else if (type == 2) {
            l = read(), r = read();
            //有序部分用trie处理，无序部分利用前缀和
            if (r <= lastN)
                printf("%lld\n", query1(r) - query1(l - 1));
            else if (l > lastN)
                printf("%lld\n", query2(l, r));
            else
                printf("%lld\n",
                       query1(lastN) - query1(l - 1) + query2(lastN + 1, r));
        } else if (type == 3) {
            X ^= read();
        } else {
            for (int k = lastN + 1; k <= n; k++) insert(a[k]);
            memset(sum[n], 0, sizeof(sum[n]));
            lastN = n, lastXor = X;
        }
    }
    return 0;
}

K Choosing The Commander

Description

CF817E Choosing The Commander

Solution

插入一个数将其访问过的节点的 $sum++$，删除一个数则 $sum--$。查询时，类似平衡树求 $rank$ 的做法。具体的，记 $l$ 的第 $i$ 位为 $l_i$，$p$ 的第 $i$ 位为 $p_i$。若 $l_i=1$,那么答案应该加上 $son[p_i]$的 $sum$，同时继续查询 $son[p_i⊕1]$；否则继续查询 $son[p_i]$。

Code

Choosing The Commander

#include <bits/stdc++.h>

using namespace std;

int n, p, l, type;
struct trie {
    trie* son[2];
    int sum;
    trie() {
        son[0] = son[1] = NULL;
        sum = 0;
    }
} * root;

template <class T>
void read(T& x, int f = 1) {
    char ch = getchar();
    x = 0;
    while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : 1), ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
    x *= f;
}

void insert(int p, int type) {
    trie* cur = root;
    for (int i = 31; ~i; i--) {
        int now = (p >> i) & 1;
        if (cur->son[now] == NULL) cur->son[now] = new trie;
        cur = cur->son[now];
        cur->sum += type;
    }
}

void query(int p, int l) {
    int ans = 0;
    trie* cur = root;
    for (int i = 31; ~i; i--) {
        bool pi = (p >> i) & 1;
        bool li = (l >> i) & 1;
        if (cur == NULL) break;
        if (li && cur->son[pi] != NULL) ans += cur->son[pi]->sum;
        cur = cur->son[pi ^ li];
    }
    printf("%d\n", ans);
}

int main() {
    read(n);
    root = new trie;
    for (int i = 1; i <= n; i++) {
        read(type), read(p);
        if (type == 1)
            insert(p, 1);
        else if (type == 2)
            insert(p, -1);
        else
            read(l), query(p, l);
    }
    return 0;
}

L CF241B Friends

Description

CF241B Friends

Solution

直接求第 $k$ 不太好处理，因为选取的是无序对，存在选取顺序问题,不然会重复。为了方便可以考虑求所有有序对的异或值，然后求前 $2k$ 大的异或值的和 ，那么答案就是求得的和的一半，这样就不需要考虑重复了。

建立好 $trie$ 树后，用类似平衡树求第 $2k$ 大的方法求出第 $2k$ 大的两两异或值 $valKth$，同时可以得到这样的值有多少个。接下来于对每一个数 $val[i]$，在 $trie$ 树上，求与之异或后大于 $valKth$ 的数的和。具体的，若 $valkth$ 第 $j$ 位为 1，那么接下来应该访问和 $val[i]$ 第 $j$ 位互补的那个儿子；否则，应该访问$val[i]$ 第 $j$ 位相同的儿子，同时统计与 $val[i]$ 在第 $j$ 位异或值为 1 的值的和。具体的统计方法是，在预处理时将 $val$ 数组排序，记录每一位上 0/1 数量的前缀和，在插入时记录每个节点对应 $val$ 的下标范围，之后根据这个范围内每一位(设为 $p$) 0/1 的个数以及 $val[i]$ 的第 $p$ 位的值按位求和即可。

Code

CF241B Friends

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int MAXN = 5e4 + 5;
const int MOD = 1e9 + 7;
const int BIT = 30;
int n, val[MAXN];
ll k, pre[MAXN][BIT + 2][2];  //每一位上0,1的个数前缀和

struct trie {
    trie* son[2];
    int sz, mx, mi;
    trie() {
        son[0] = son[1] = NULL;
        sz = mx = mi = 0;
    }
} * root;

ll qpow(ll a, ll b) {
    ll ans = 1, base = a;
    while (b) {
        if (b & 1) ans = ans * base % MOD;
        b >>= 1, base = base * base % MOD;
    }
    return ans;
}

void insert(int& id) {
    trie* cur = root;
    for (int i = BIT; ~i; i--) {
        int now = (val[id] >> i) & 1;
        if (cur->son[now] == NULL) cur->son[now] = new trie;
        cur = cur->son[now];
        cur->sz++;
        cur->mx = id;
        cur->mi = (cur->mi ? cur->mi : id);
    }
}

ll getKth(ll& k) {
    ll ans = 0;
    trie* nodePtr[MAXN];
    for (int i = 1; i <= n; i++) nodePtr[i] = root;
    for (int j = BIT; ~j; j--) {
        ll tmp = 0;
        bool tag = 1;
        for (int i = 1; i <= n; i++)
            if (nodePtr[i] != NULL &&
                nodePtr[i]->son[((val[i] >> j) & 1) ^ 1] != NULL)
                tmp += nodePtr[i]->son[((val[i] >> j) & 1) ^ 1]->sz;
        if (tmp >= k)  //该位选1的方案数>=k，则第k大的在这一位必为1
            ans |= 1ll << j;
        else  //该位选1的方案数<k，则第k大的在这一位必为0，且排名<=k-该位选1的方案数
            k -= tmp, tag = 0;
        for (int i = 1; i <= n; i++)
            if (nodePtr[i])
                nodePtr[i] = nodePtr[i]->son[((val[i] >> j) & 1) ^ tag];
    }
    return ans;
}

void getSum(ll k) {
    ll valKth = getKth(k);
    ll ans = valKth * k % MOD;
    for (int i = 1; i <= n; i++) {
        //对于每一个数，求与之异或后大于valKth的数的和
        trie* cur = root;
        for (int j = BIT; ~j; j--) {
            if (cur == NULL) break;
            if ((valKth >> j) & 1)
                cur = cur->son[((val[i] >> j) & 1) ^ 1];
            else {
                if (cur->son[((val[i] >> j) & 1) ^ 1] != NULL) {
                    int l = cur->son[((val[i] >> j) & 1) ^ 1]->mi - 1;
                    int r = cur->son[((val[i] >> j) & 1) ^ 1]->mx;
                    for (int p = BIT; ~p; p--) {
                        if ((val[i] >> p) & 1)
                            ans += (pre[r][p][0] - pre[l][p][0]) << p;
                        else
                            ans += (pre[r][p][1] - pre[l][p][1]) << p;
                        ans %= MOD;
                    }
                }
                cur = cur->son[(val[i] >> j) & 1];
            }
        }
    }
    cout << ans * qpow(2, MOD - 2) % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> k;
    k *= 2;
    for (int i = 1; i <= n; i++) cin >> val[i];
    sort(val + 1, val + n + 1);
    root = new trie;
    for (int i = 1; i <= n; i++) insert(i);
    for (int j = BIT; ~j; j--)
        for (int i = 1; i <= n; i++) {
            pre[i][j][0] = pre[i - 1][j][0] + !((val[i] >> j) & 1);
            pre[i][j][1] = pre[i - 1][j][1] + ((val[i] >> j) & 1);
        }
    getSum(k);
    return 0;
}

L 十二省联考2019 异或粽子

Description

P5283 十二省联考2019 异或粽子

Solution

上一题的弱化版。本机运行时可能炸内存，可以适当调小 MAXN 的值。

Code

十二省联考2019 异或粽子

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int MAXN = 5e5 + 5;
const int BIT = 31;
int n;
ll k, pre[MAXN][BIT + 1][2], val[MAXN], x;
struct trie {
    trie* son[2];
    int sz, mx, mi;
    trie() {
        son[0] = son[1] = NULL;
        sz = mx = mi = 0;
    }
} * root;

void insert(int& id) {
    trie* cur = root;
    for (int i = BIT; ~i; i--) {
        int now = (val[id] >> i) & 1;
        if (cur->son[now] == NULL) cur->son[now] = new trie;
        cur = cur->son[now];
        cur->sz++;
        cur->mx = id;
        cur->mi = (cur->mi ? cur->mi : id);
    }
}

ll getKth(ll& k) {
    ll ans = 0;
    trie* nodePtr[MAXN];
    for (int i = 1; i <= n + 1; i++) nodePtr[i] = root;
    for (int j = BIT; ~j; j--) {
        ll tmp = 0;
        bool tag = 1;
        for (int i = 1; i <= n + 1; i++)
            if (nodePtr[i] != NULL &&
                nodePtr[i]->son[((val[i] >> j) & 1) ^ 1] != NULL)
                tmp += nodePtr[i]->son[((val[i] >> j) & 1) ^ 1]->sz;
        if (tmp >= k)
            ans |= 1ll << j;
        else
            k -= tmp, tag = 0;
        for (int i = 1; i <= n + 1; i++)
            if (nodePtr[i])
                nodePtr[i] = nodePtr[i]->son[((val[i] >> j) & 1) ^ tag];
    }
    return ans;
}

void getSum(ll k) {
    ll valKth = getKth(k);
    ll ans = valKth * k;
    for (int i = 1; i <= n + 1; i++) {
        trie* cur = root;
        for (int j = BIT; ~j; j--) {
            if (cur == NULL) break;
            if ((valKth >> j) & 1)
                cur = cur->son[((val[i] >> j) & 1) ^ 1];
            else {
                if (cur->son[((val[i] >> j) & 1) ^ 1] != NULL) {
                    int l = cur->son[((val[i] >> j) & 1) ^ 1]->mi - 1;
                    int r = cur->son[((val[i] >> j) & 1) ^ 1]->mx;
                    for (int p = BIT; ~p; p--) {
                        if ((val[i] >> p) & 1)
                            ans += (pre[r][p][0] - pre[l][p][0]) << p;
                        else
                            ans += (pre[r][p][1] - pre[l][p][1]) << p;
                    }
                }
                cur = cur->son[(val[i] >> j) & 1];
            }
        }
    }
    cout << ans / 2;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> k;
    k *= 2;
    val[1] = 0;
    for (int i = 2; i <= n + 1; i++) {
        cin >> x;
        val[i] = val[i - 1] ^ x;
    }
    sort(val + 1, val + n + 2);
    root = new trie;
    for (int i = 1; i <= n + 1; i++) insert(i);
    for (int j = BIT; ~j; j--)
        for (int i = 1; i <= n + 1; i++) {
            pre[i][j][0] = pre[i - 1][j][0] + !((val[i] >> j) & 1);
            pre[i][j][1] = pre[i - 1][j][1] + ((val[i] >> j) & 1);
        }
    getSum(k);
    return 0;
}

M CF1055F Tree and XOR

Description

CF1055F Tree and XOR

Solution

做法同 CF241B Friends。不过按照 CF241B Friends 的做法空间复杂度为 $O(61*N)$，显然不可能把整个 $trie$ 树存进去。实际上，只求第 $k$ 大的话有用的只有一层节点，当访问到下一层时，将上一层节点删除就好了。这样空间复杂度变为 $O(N)$，时间复杂度依然为$O(61*N)$。

注: 用系统自带的 $delete$ 时不知道为何 $RE$ 了，这里手写了 $new$ 和 $delete$ 操作。

Code

CF1055F Tree and XOR

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int MAXN = 1e6 + 5;
const int BIT = 61;
int n, p[MAXN],u,tot[2];
ll k, val[MAXN], v;

template<class T>
void read(T &x, int f = 1) {
  char ch = getchar();
  x = 0;
  while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : 1), ch = getchar();
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
  x *= f;
}

struct trie {
  trie* son[2];
  int sz;
  trie() {
    son[0] = son[1] = NULL;
    sz = 0;
  }
}*root,node[MAXN][2];

trie* newNode(trie* &cur,bool tag) {
  return cur=&node[tot[tag]++][tag];
}

void getKth(ll k) {
  ll ans = 0;
  newNode(root,0);
  trie *nodePtr[MAXN],*valPtr[MAXN];
  for (int i = 1; i <= n; i++) nodePtr[i] = valPtr[i] = root;
  for (int j = BIT; ~j; j--) {
    ll tmp = 0;
    bool tag = 0;
    for (int i = 1; i <= n; i++) {
      if (valPtr[i]->son[((val[i] >> j) & 1)] == NULL)
        newNode(valPtr[i]->son[((val[i] >> j) & 1)],j&1);
      valPtr[i] = valPtr[i]->son[((val[i] >> j) & 1)];
      valPtr[i]->sz++;
    }
    for (int i = 1; i <= n; i++)
      if (nodePtr[i] != NULL && nodePtr[i]->son[((val[i] >> j) & 1)] != NULL)
        tmp += nodePtr[i]->son[((val[i] >> j) & 1)]->sz;
    if (tmp < k) {
      k -= tmp, tag = 1;
      ans |= 1ll << j;
    }
    for (int i = 1; i <= n; i++)
      if (nodePtr[i] != NULL)
        nodePtr[i] = nodePtr[i]->son[((val[i] >> j) & 1) ^ tag];
    for(int i=0; i<=tot[(j&1)^1]; i++) {
      node[i][(j&1)^1].son[0]=node[i][(j&1)^1].son[1]=NULL;
      node[i][(j&1)^1].sz=0;
    }
    tot[(j&1)^1]=0;
  }
  cout << ans;
}

struct edge {
  int nxt, to;
  ll val;
} e[MAXN];

void addEdge(int from, int to, ll val) {
  static int t;
  e[t].val = val, e[t].to = to, e[t].nxt = p[from], p[from] = t++;
}

void dfs(int now, ll v) {
  val[now] = v;
  for (int i = p[now]; ~i; i = e[i].nxt) {
    int to = e[i].to;
    if (!val[to]) dfs(to, v ^ e[i].val);
  }
}

int main() {
  read(n),read(k);
  memset(p, -1, sizeof(p));
  for (int i = 1; i <= n - 1; i++) {
    read(u), read(v);
    addEdge(u, i + 1, v);
  }
  dfs(1, 0);
  getKth(k);
  return 0;
}

Level IV

可持久化 $Trie$ 树,原理和可持久化线段树相同

A 最大异或和

Description

P4735 最大异或和

Solution

记 $preXor_i$ 表示前 $i$ 个数的异或和。对于查询操作，用异或性质转化一下，只需要求 $preXor_N⊕x$ 异或上 $preXor_{p-1}$ 的最大值（$l-1<=p<=r-1$），即在 $r-1$ 版本的 $trie$ 树中求插入时间大于等于 $l-1$ 的数与 $preXor_N⊕x$ 的最大异或和。因此每个点记一个 $last$，表示最后访问的时间，当 $last\ge l-1$时才可能被计入答案。

Code

最大异或和

#include <bits/stdc++.h>

using namespace std;
const int MAXN = 3e5 + 5;

int n, m, l, r;
int preXor, x;
char type[2];
struct trie {
    trie *son[2];
    int last;
    trie() {
        son[0] = son[1] = NULL;
        last = 0;
    }
} node[MAXN * 48], *root[MAXN * 2];

void read(int &x, int f = 1) {
    char ch = getchar();
    x = 0;
    while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : 1), ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
}

trie *newNode(trie *&cur) {
    static int cntNode;
    return cur = &node[cntNode++];
}

void initR0() {
    trie *cur = newNode(root[0]);
    for (register int i = 23; i >= 0; i--) cur = newNode(cur->son[0]);
}

void build(const int &id) {
    trie *cur = newNode(root[id]), *pre = root[id - 1];
    for (register int i = 23; ~i; i--) {
        int now = (preXor >> i) & 1;
        if (pre != NULL) {
            cur->son[now ^ 1] = pre->son[now ^ 1];
            pre = pre->son[now];
        }
        cur = newNode(cur->son[now]);
        cur->last = id;
    }
}

void query(trie *cur, const int &last, const int &val) {
    int ans = 0;
    for (register int i = 23; ~i; i--) {
        int now = (val >> i) & 1;
        trie *tmp = cur->son[now ^ 1];
        if (tmp != NULL && tmp->last >= last)
            cur = tmp, ans += 1 << i;
        else
            cur = cur->son[now];
    }
    printf("%d\n", ans);
}

int main() {
    read(n), read(m);
    initR0();
    for (int i = 1; i <= n; i++) {
        read(x);
        preXor ^= x;
        build(i);
    }
    for (int i = 1; i <= m; i++) {
        scanf("%s", type);
        if (type[0] == 'A') {
            read(x);
            preXor ^= x;
            build(++n);
        } else {
            read(l), read(r), read(x);
            query(root[r - 1], l - 1, preXor ^ x);
        }
    }
    return 0;
}

B TJOI2018 异或

Description

P4592 TJOI2018 异或

Solution

对于询问 1，按dfs序建立可持久化 $trie$ 树；对于询问 2，按深度建立可持久化 $trie$ 树，查询的时候求一下 $lca$ 即可。

Code

TJOI2018 异或

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 5;
const int BIT = 29;
int n, q, u, v, opt, z;
int p[MAXN], fa[MAXN][18], depth[MAXN];
int in[MAXN], out[MAXN], val[MAXN];

void read(int &x, int f = 1) {
    char ch = getchar();
    x = 0;
    while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : 1), ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
    x *= f;
}

struct trie {
    trie *son[2];
    int last;
    trie() {
        son[0] = son[1] = NULL;
        last = 0;
    }
} node[MAXN * (BIT + 2)][2], *root[MAXN][2];

trie *newNode(trie *&cur, const bool &tag) {
    static int cntNode[2];
    return cur = &node[cntNode[tag]++][tag];
}

void initRoot() {
    trie *cur = newNode(root[1][0], 0);
    trie *tmp = newNode(root[1][1], 1);
    for (int i = BIT; ~i; i--) {
        int now = (val[1] >> i) & 1;
        cur = newNode(cur->son[now], 0);
        tmp = newNode(tmp->son[now], 1);
        cur->last = tmp->last = 1;
    }
}

void insert(trie *pre, trie *cur, int val, int last, bool tag) {
    for (int i = BIT; ~i; i--) {
        int now = (val >> i) & 1;
        if (pre != NULL) {
            cur->son[now ^ 1] = pre->son[now ^ 1];
            pre = pre->son[now];
        }
        cur = newNode(cur->son[now], tag);
        cur->last = last;
    }
}

int query(trie *cur, int val, int last) {
    int ans = 0;
    for (int i = BIT; ~i; i--) {
        int now = (val >> i) & 1;
        if (cur->son[now ^ 1] != NULL && cur->son[now ^ 1]->last >= last)
            cur = cur->son[now ^ 1], ans += 1 << i;
        else if (cur->son[now] != NULL && cur->son[now]->last >= last)
            cur = cur->son[now];
        else
            break;
    }
    return ans;
}

struct edge {
    int to, nxt;
} e[MAXN * 2];

void addEdge(int from, int to) {
    static int t;
    e[t].to = to, e[t].nxt = p[from], p[from] = t++;
}

void dfs1(const int &now) {
    static int times = 1;
    in[now] = times++;
    for (int i = p[now]; ~i; i = e[i].nxt) {
        int to = e[i].to;
        if (!in[to]) {
            insert(root[times - 1][0], newNode(root[times][0], 0), val[to],
                   times, 0);
            dfs1(to);
        }
    }
    out[now] = times;
}

void dfs2(int now, int d) {
    depth[now] = d;
    for (int i = p[now]; ~i; i = e[i].nxt) {
        int to = e[i].to;
        if (!depth[to]) {
            fa[to][0] = now;
            insert(root[now][1], newNode(root[to][1], 1), val[to], d + 1, 1);
            dfs2(to, d + 1);
        }
    }
}

void getFa() {
    for (int j = 1; (1 << j) <= n; j++)
        for (int i = 1; i <= n; i++)
            if (fa[i][j - 1]) fa[i][j] = fa[fa[i][j - 1]][j - 1];
}

int lca(int a, int b, int i = 0) {
    if (depth[a] < depth[b]) swap(a, b);
    for (; (1 << i) <= depth[a]; i++)
        ;
    for (int j = i - 1; j >= 0; j--)
        if (depth[a] - depth[b] >= (1 << j)) a = fa[a][j];
    if (a == b) return a;
    for (int j = i - 1; j >= 0; j--)
        if (fa[a][j] && fa[a][j] != fa[b][j]) a = fa[a][j], b = fa[b][j];
    return fa[a][0];
}

int main() {
    read(n), read(q);
    for (int i = 1; i <= n; i++) read(val[i]);
    memset(p, -1, sizeof(p));
    for (int i = 1; i <= n - 1; i++) {
        read(u), read(v);
        addEdge(u, v), addEdge(v, u);
    }
    initRoot();
    dfs1(1);
    dfs2(1, 1);
    getFa();
    for (int i = 1; i <= q; i++) {
        read(opt);
        if (opt == 1) {
            read(u), read(z);
            printf("%d\n", query(root[out[u] - 1][0], z, in[u]));
        } else {
            read(u), read(v), read(z);
            int tmp = lca(u, v);
            printf("%d\n", max(query(root[u][1], z, depth[tmp]),
                               query(root[v][1], z, depth[tmp])));
        }
    }
    return 0;
}

C JSOI2015 字符串树

Description

P6088 JSOI2015 字符串树

Solution

$dfs$ 时，对每个点，在其父亲版本的基础上建立可持久化 $trie$ 树。令$cnt_i$ 表示从根到节点到 $i$ 有多少字符串以 $S$ 为前缀。显然，答案具有可加性，$u,v$ 之间以 $S$ 为前缀的字符串数目为 $cnt_u + cnt_v - 2*cnt_{lca(u,v)}$，查询的时候求一下 $lca$ 即可。

Code

JSOI2015 字符串树

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
int n, m, u, v;
char s[11];
int p[MAXN], fa[MAXN][17], depth[MAXN];
void read(int& x, int f = 1) {
    char ch = getchar();
    x = 0;
    while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : 1), ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
    x *= f;
}
struct trie {
    trie* son[26];
    int cnt;
    trie() {
        for (int i = 0; i < 26; i++) son[i] = NULL;
        cnt = 0;
    }
} node[MAXN * 10], *root[MAXN];
trie* newNode(trie*& cur) {
    static int cntNode;
    return cur = &node[cntNode++];
}
struct edge {
    int to, nxt;
    string s;
} e[MAXN * 2];
void addEdge(int from, int to, const string& s) {
    static int t;
    e[t].s = s, e[t].to = to, e[t].nxt = p[from], p[from] = t++;
}
void build(trie* pre, trie* cur, const string& s) {
    for (int i = 0; i < s.size(); i++) {
        int to = s[i] - 'a';
        if (pre != NULL) {
            for (int j = 0; j < 26; j++) cur->son[j] = pre->son[j];
            pre = pre->son[to];
        }
        cur = newNode(cur->son[to]);
        cur->cnt = (pre != NULL ? pre->cnt : 0) + 1;
    }
}
int query(trie* cur, const string& s) {
    for (int i = 0; i < s.size(); i++) {
        int to = s[i] - 'a';
        if (cur->son[to] != NULL)
            cur = cur->son[to];
        else
            return 0;
    }
    return cur->cnt;
}
void dfs(const int& now, int d) {
    depth[now] = d;
    for (int i = p[now]; ~i; i = e[i].nxt) {
        int to = e[i].to;
        if (!depth[to] && to != 1) {
            fa[to][0] = now;
            build(root[now], newNode(root[to]), e[i].s);
            dfs(to, d + 1);
        }
    }
}
void getFa() {
    for (int j = 1; (1 << j) <= n; j++)
        for (int i = 1; i <= n; i++)
            if (fa[i][j - 1]) fa[i][j] = fa[fa[i][j - 1]][j - 1];
}
int lca(int a, int b, int i = 0) {
    if (depth[a] < depth[b]) swap(a, b);
    for (; (1 << i) <= depth[a]; i++);
    for (int j = i - 1; j >= 0; j--)
        if (depth[a] - depth[b] >= (1 << j)) a = fa[a][j];
    if (a == b) return a;
    for (int j = i - 1; j >= 0; j--)
        if (fa[a][j] && fa[a][j] != fa[b][j]) a = fa[a][j], b = fa[b][j];
    return fa[a][0];
}
int main() {
    memset(p, -1, sizeof(p));
    read(n);
    for (int i = 1; i <= n - 1; i++) {
        read(u), read(v), scanf("%s", s);
        addEdge(u, v, s), addEdge(v, u, s);
    }
    newNode(root[1]);
    dfs(1, 0);
    getFa();
    read(m);
    for (int i = 1; i <= m; i++) {
        read(u), read(v), scanf("%s", s);
        printf("%d\n", query(root[u], s) + query(root[v], s) -
                           2 * query(root[lca(u, v)], s));
    }
    return 0;
}

C HEOI2013 ALO

Description

P4098 HEOI2013 ALO

Solution

首先建立可持久化 $trie$ 树。对于 $a_i$，设左边第一个比它大的数下标为 $l_1$, 左边第二个比它大的数下标为 $l_2$；右边第一个比它大的数下标为 $r_1$, 左边第二个比它大的数下标为 $r_2$。显然，能让 $a_i$ 为次大值的最大区间为 $[l_1+1,r_2-1]$ 和 $[l_2+1,r_1-1]$。只需预处理出 $l_{1,2}$ 和 $r_{1,2}$，接下来在可持久化 $trie$ 上贪心地求最大值即可。

考虑如何求 $l_{1,2}$ 和 $r_{1,2}$。将 $a_1$ 到 $a_n$ 按从大到小排序，同时记录原来的下标 $b_i$。排序后按顺序将 $b_i$ 插入 $set$ 中。易知 $set$ 中任意元素 $b_k$ 对应值 $a_{b_k}$一定大于当前位置 $b_i$ 对应值 $a_{b_i}$(题目约定数组 $a$ 中的元素不重复), 且 $set$ 已按下标排好序，用 lower_bound 和 upper_bound 容易求出当前下标 $b_i$ 的前驱和后继。

Code

HEOI2013 ALO

#include <bits/stdc++.h>

using namespace std;
const int MAXN = 5e4 + 5;
const int BIT = 30;
int n, a[MAXN], b[MAXN], l[MAXN][3], r[MAXN][3];

template <class T>
void read(T &x, int f = 1) {
    char ch = getchar();
    x = 0;
    while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : 1), ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
    x *= f;
}

struct trie {
    trie *son[2];
    int last;
    trie() {
        son[0] = son[1] = NULL;
        last = 0;
    }
} * root[MAXN];

void insert(int id) {
    trie *cur = root[id] = new trie, *pre = root[id - 1];
    for (int i = BIT; ~i; i--) {
        int now = (a[id] >> i) & 1;
        if (pre != NULL) {
            cur->son[now ^ 1] = pre->son[now ^ 1];
            pre = pre->son[now];
        }
        cur->son[now] = new trie;
        cur = cur->son[now];
        cur->last = id;
    }
}

int query(trie *cur, int last, int val) {
    int ans = 0;
    for (int i = BIT; ~i; i--) {
        int now = (val >> i) & 1;
        if (cur->son[now ^ 1] != NULL && cur->son[now ^ 1]->last >= last)
            cur = cur->son[now ^ 1], ans |= 1 << i;
        else
            cur = cur->son[now];
    }
    return ans;
}

bool cmp(const int &x, const int &y) { return a[x] > a[y]; }

int main() {
    read(n);
    root[0] = new trie;
    for (int i = 1; i <= n; i++) read(a[i]), insert(i), b[i] = i;
    sort(b + 1, b + n + 1, cmp);
    set<int> s;
    set<int>::iterator it;
    s.insert(-2), s.insert(-1), s.insert(n + 1), s.insert(n + 2);
    for (int i = 1; i <= n; i++) {
        s.insert(b[i]);
        it = s.lower_bound(b[i]);
        l[b[i]][1] = max(0, *--it);
        l[b[i]][2] = max(0, *--it);
        it = s.upper_bound(b[i]);
        r[b[i]][1] = min(n + 1, *it);
        r[b[i]][2] = min(n + 1, *++it);
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
        ans = max(ans, max(query(root[r[i][1] - 1], l[i][2] + 1, a[i]),
                           query(root[r[i][2] - 1], l[i][1] + 1, a[i])));
    printf("%d", ans);
    return 0;
}