bzoj3489

kdtree

3维kdtree，就是三个维度轮换着切，我们把每个元素看成一个点，坐标是上次出现的位置，下次出现的位置，自己的位置，第一个<l,第二个>r,第三个[l,r],然后kdtree上爆搜剪枝就行了。

kdtree看起来能解决所有偏序问题。

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + , inf = 1e9;

int rd()

{

    int x = , f = ; char c = getchar();

    while(c < '' || c > '') { if(c == '-') f = -; c = getchar(); }

    while(c >= '' && c <= '') { x = x *  + c - ''; c = getchar(); }

    return x * f;

}

int n, m, root, d, ans;

int last[N];

struct data {

    int p[], mn[], mx[], lc, rc, ans, val;

    bool friend operator < (const data &a, const data &b) {

        if(a.p[d] != b.p[d]) return a.p[d] < b.p[d];

        if(a.p[(d + ) % ] != b.p[(d + ) % ]) return a.p[(d + ) % ] < b.p[(d + ) % ];

        if(a.p[(d + ) % ] != b.p[(d + ) % ]) return a.p[(d + ) % ] < b.p[(d + ) % ];

    }

} a[N];

void update(int x)

{

    int lc = a[x].lc, rc = a[x].rc;

    for(int i = ; i < ; ++i)

    {

        a[x].mn[i] = min(a[x].p[i], min(a[lc].mn[i], a[rc].mn[i]));

        a[x].mx[i] = max(a[x].p[i], max(a[lc].mx[i], a[rc].mx[i]));

    }

    a[x].ans = max(a[x].val, max(a[lc].ans, a[rc].ans));

}

int build(int l, int r, int D)

{

    if(l > r) return ;

    d = D;

    int mid = (l + r) >> ;

    nth_element(a + l, a + mid, a + r + );

    a[mid].lc = build(l, mid - , (D + ) % );

    a[mid].rc = build(mid + , r, (D + ) % );

    update(mid);

    return mid;

}

bool out(int k, int l, int r)

{

    return ans < a[k].ans && a[k].mn[] <= r && a[k].mx[] >= l && a[k].mn[] < l && a[k].mx[] > r;

}

void query(int k, int l, int r)

{

    if(!k || !out(k, l, r)) return;

    if(a[k].mx[] <= r && a[k].mn[] >= l && a[k].mx[] < l && a[k].mn[] > r)

    {

        ans = max(ans, a[k].ans);

        return;

    }

    if(a[k].p[] <= r && a[k].p[] >= l && a[k].p[] < l && a[k].p[] > r) ans = max(ans, a[k].val);

    query(a[k].lc, l, r);

    query(a[k].rc, l, r);

}

int main()

{

    for(int i = ; i < ; ++i) a[].mn[i] = inf, a[].mx[i] = a[].ans = -inf;

    n = rd();

    m = rd();

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

    {

        a[i].val = rd();

        a[i].p[] = i;

        a[i].p[] = last[a[i].val];

        a[last[a[i].val]].p[] = i;

        last[a[i].val] = i;

    }

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

        if(!a[i].p[])

            a[i].p[] = n + ;

    root = build(, n, );

    while(m--)

    {

        int l = (rd() + ans) % n + , r = (rd() + ans) % n + ;

        if(l > r) swap(l, r);

        ans = ;

        query(root, l, r);

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

    }

    return ;

}