【题解】BZOJ3489 A Hard RMQ problem(主席树套主席树)

【题解】A simple RMQ problem

占坑，免得咕咕咕了，争取在2h内写出代码

upd:由于博主太菜而且硬是要用指针写两个主席树，所以延后2hQAQ

upd:由于博主太菜而且太懒所以他决定写kd tree了

upd:由于博主太菜而且太懒所以他不写代码了(实际上是写了6k之后崩溃了)

所以直接口胡题解

题目大意：

因为是OJ上的题，就简单点好了。给出一个长度为n的序列，给出M个询问：在[l,r]之间找到一个在这个区间里只出现过一次的数，并且要求找的这个数尽可能大。如果找不到这样的数，则直接输出0。我会采取一些措施强制在线。

好就是这样

解法:

我本来是想直接对值域线段树可持久化，然后类似于吉司机线段树一样维护最小值和次小值...发现不会查一个区间，于是我们可以这样：

每个位置记录i一个上一次出现的\(pre\)和下一次出现的\(next\)，把所有数先按照\(pre\)从小往大排序，对于每一个位置，维护一个数组，数组的下标是next[i]，数组里面的值是data[i]，查询的时候查询查询这个数组\([r+1,n+1]\)中的最大值是多少，就是我们的答案。可持久化数组可以用主席树维护，前缀\(pre\)的\(next\)可以用主席树维护，所以只要主席树套主席树就\(ok\)了。

时空复杂度\(O(n \log^2 n)\)

#include <iostream>

#include <cstdlib>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <algorithm>

using namespace std;

inline void Read(int &Num) {

    char c = getchar();

    bool Neg = false;

    while (c < '0' || c > '9') {

        if (c == '-')

            Neg = true;

        c = getchar();

    }

    Num = c - '0';

    c = getchar();

    while (c >= '0' && c <= '9') {

        Num = Num * 10 + c - '0';

        c = getchar();

    }

    if (Neg)

        Num = -Num;

}

inline int gmin(int a, int b) { return a < b ? a : b; }

inline int gmax(int a, int b) { return a > b ? a : b; }

const int MaxN = 100000 + 5, MaxNodeI = 2000000 + 5, MaxNodeII = 40000000 + 5;

int n, m, Ans, IndexI, IndexII;

int Last[MaxN], Root_I[MaxN], Son_I[MaxNodeI][2], Root_II[MaxNodeI], Son_II[MaxNodeII][2], T[MaxNodeII];

struct ES {

    int Pos, Num, Prev, Next;

    bool operator<(const ES &b) const { return Prev < b.Prev; }

    bool operator<(const int &b) const { return Prev < b; }

} E[MaxN];

void Insert_II(int &x, int Last, int s, int t, int Pos, int Num) {

    if (x == 0)

        x = ++IndexII;

    T[x] = gmax(T[Last], Num);

    if (s == t)

        return;

    int m = (s + t) >> 1;

    if (Pos <= m) {

        Son_II[x][1] = Son_II[Last][1];

        Insert_II(Son_II[x][0], Son_II[Last][0], s, m, Pos, Num);

    } else {

        Son_II[x][0] = Son_II[Last][0];

        Insert_II(Son_II[x][1], Son_II[Last][1], m + 1, t, Pos, Num);

    }

}

void Insert_I(int &x, int Last, int s, int t, int Nxt, int Pos, int Num) {

    if (x == 0)

        x = ++IndexI;

    Insert_II(Root_II[x], Root_II[Last], 0, n + 1, Pos, Num);

    if (s == t)

        return;

    int m = (s + t) >> 1;

    if (Nxt <= m) {

        Son_I[x][1] = Son_I[Last][1];

        Insert_I(Son_I[x][0], Son_I[Last][0], s, m, Nxt, Pos, Num);

    } else {

        Son_I[x][0] = Son_I[Last][0];

        Insert_I(Son_I[x][1], Son_I[Last][1], m + 1, t, Nxt, Pos, Num);

    }

}

int Get_II(int x, int s, int t, int l, int r) {

    if (x == 0)

        return 0;

    if (l <= s && r >= t)

        return T[x];

    int ret = 0, m = (s + t) >> 1;

    if (l <= m)

        ret = gmax(ret, Get_II(Son_II[x][0], s, m, l, r));

    if (r >= m + 1)

        ret = gmax(ret, Get_II(Son_II[x][1], m + 1, t, l, r));

    return ret;

}

int Get_I(int x, int s, int t, int l_I, int r_I, int l_II, int r_II) {

    if (x == 0)

        return 0;

    if (l_I <= s && r_I >= t)

        return Get_II(Root_II[x], 0, n + 1, l_II, r_II);

    int ret = 0, m = (s + t) >> 1;

    if (l_I <= m)

        ret = gmax(ret, Get_I(Son_I[x][0], s, m, l_I, r_I, l_II, r_II));

    if (r_I >= m + 1)

        ret = gmax(ret, Get_I(Son_I[x][1], m + 1, t, l_I, r_I, l_II, r_II));

    return ret;

}

int main() {

    scanf("%d%d", &n, &m);

    for (int i = 1; i <= n; ++i) {

        Read(E[i].Num);

        E[i].Pos = i;

        E[i].Prev = Last[E[i].Num];

        E[E[i].Prev].Next = i;

        E[i].Next = n + 1;

        Last[E[i].Num] = i;

    }

    sort(E + 1, E + n + 1);

    for (int i = 1; i <= n; ++i) Insert_I(Root_I[i], Root_I[i - 1], 0, n + 1, E[i].Next, E[i].Pos, E[i].Num);

    Ans = 0;

    int x, y, l, r, p;

    for (int i = 1; i <= m; ++i) {

        Read(x);

        Read(y);

        l = gmin((x + Ans) % n + 1, (y + Ans) % n + 1);

        r = gmax((x + Ans) % n + 1, (y + Ans) % n + 1);

        p = lower_bound(E + 1, E + n + 1, l) - E - 1;

        Ans = Get_I(Root_I[p], 0, n + 1, r + 1, n + 1, l, r);

        printf("%d\n", Ans);

    }

    return 0;

}

巴特西

【题解】BZOJ3489 A Hard RMQ problem(主席树套主席树)

【题解】A simple RMQ problem

最新文章

热门文章