BZOJ 3489: A simple rmq problem(K-D Tree)

#include<cstdio>
#include<cstring>
#include<algorithm>
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2)? EOF : *p1++)
using namespace std;
const int MAXN = 1e6 + 10;
char buf[1 << 21], *p1 = buf, *p2 = buf;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, M, root, WD;
int Ql, Qr, lastans = 0;
struct Point {
    int x[4];
    bool operator < (const Point &rhs) const{
        return x[WD] < rhs.x[WD];
    }
}P[MAXN];
#define ls(x) T[x].ls
#define rs(x) T[x].rs
struct KDTree {
    int ls, rs, mn[3], mx[3], val;
    Point tp; 
}T[MAXN];
int a[MAXN], pre[MAXN], nxt[MAXN], happen[MAXN];
void update(int k) {
    for(int i = 0; i <= 2; i++) {
        T[k].mn[i] = T[k].mx[i] = T[k].tp.x[i];
        if(ls(k)) T[k].mn[i] = min(T[ls(k)].mn[i], T[k].mn[i]), T[k].mx[i] = max(T[ls(k)].mx[i], T[k].mx[i]);
        if(rs(k)) T[k].mn[i] = min(T[rs(k)].mn[i], T[k].mn[i]), T[k].mx[i] = max(T[rs(k)].mx[i], T[k].mx[i]);
    }
    T[k].val = max(T[k].tp.x[3], T[ls(k)].val);
    T[k].val = max(T[k].val, T[rs(k)].val);
}
int Build(int l, int r, int wd) {
    if(l > r) return 0;
    int mid = l + r >> 1; WD = wd;
    nth_element(P + l, P + mid, P + r + 1);
    T[mid].tp = P[mid];
    ls(mid) = Build(l, mid - 1, (wd + 1) % 3);
    rs(mid) = Build(mid + 1, r, (wd + 1) % 3);
    update(mid);
    return mid;
}
bool CheckInclude(int k) {
    if(T[k].mn[0] >= Ql && T[k].mx[0] <= Qr
    && T[k].mx[1] < Ql && T[k].mn[2] > Qr) return 1;
    return 0;
}
bool CheckCross(int k) {
    if(T[k].tp.x[0] >= Ql && T[k].tp.x[0] <= Qr
    && T[k].tp.x[1] < Ql && T[k].tp.x[2] > Qr) return 1;
    return 0;    
} 
bool CheckNotCross(int k) {
    if(T[k].mn[1] >= Ql || T[k].mx[2] <= Qr || T[k].mx[0] < Ql  || T[k].mn[0] > Qr) return 1;
    return 0; 
}
void Query(int k) {
    if(CheckInclude(k)) {
        lastans = max(lastans, T[k].val); return ; //矩形完全包含在查询区间内 
    }
    if(CheckCross(k)) 
        lastans = max(lastans, T[k].tp.x[3]); //相交 
    if(CheckNotCross(k)) return ; // 没有重合的地方 
    int disl = T[ls(k)].val, disr = T[rs(k)].val;
    if(disl > disr) {
        if(disl > lastans) Query(ls(k));
        if(disr > lastans) Query(rs(k));
    }
    else {
        if(disr > lastans) Query(rs(k));
        if(disl > lastans) Query(ls(k));
    }
}
int main() {
    #ifdef WIN32
    freopen("a.in", "r", stdin);
    freopen("a.out", "w", stdout);
    #endif
    N = read(); M = read();
    for(int i = 1; i <= N; i++) a[i] = read();
    for(int i = 1; i <= N; i++) pre[i] = happen[a[i]], happen[a[i]] = i;
    for(int i = 1; i <= N; i++) happen[a[i]] = N + 1;
    for(int i = N; i >= 1; i--) nxt[i] = happen[a[i]], happen[a[i]] = i;
    for(int i = 1; i <= N; i++)
        P[i] = (Point) {i, pre[i], nxt[i], a[i]};
    root = Build(1, N, 0);
    for(int i = 1; i <= M; i++) {
        int x = read(), y = read(); 
        Ql = min((x + lastans) % N + 1,(y + lastans) % N + 1);
        Qr = max((x + lastans) % N + 1,(y + lastans) % N + 1);
        lastans = 0;
        Query(root);
        printf("%d\n", lastans);
    }
    return 0;
}