BZOJ3489 A simple rmq problem K-D Tree

传送门

什么可持久化树套树才不会写呢，K-D Tree大法吼啊

对于第\(i\)个数，设其前面最后的与它值相同的位置为\(pre_i\)，其后面最前的与它值相同的位置为\(aft_i\)，那么对于一个询问\((l,r)\)和一个位置\(i\)，需要同时满足\(pre_i < l \leq i \leq r < aft_i\)时，第\(i\)个位置的值才能产生贡献。

将\((pre_i , i , aft_i)\)看作三维空间中的一个点，那么能够产生贡献的一些点就会在一个立方体范围内。使用K-D Tree进行搜索即可。

记得要加一些剪枝，比如当前访问的区域的最大值比当前答案小就退出等

记得一定不要把nth_element(n + l , n + mid , n + r + 1)写成nth_elemet(n + l , n + r + 1 , n + mid)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
//This code is written by Itst
using namespace std;

inline int read(){
    int a = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c) && c != EOF){
    if(c == '-')
        f = 1;
    c = getchar();
    }
    if(c == EOF)
    exit(0);
    while(isdigit(c)){
    a = a * 10 + c - 48;
    c = getchar();
    }
    return f ? -a : a;
}

const int MAXN = 1e5 + 7;
struct node{
    int pos[3] , val;
}nd[MAXN];
int N , M , lastans , ind[MAXN];
int pre[MAXN] , ch[MAXN][2] , maxV[MAXN] , maxP[MAXN][3] , minP[MAXN][3];

bool cmp0(node a , node b){return a.pos[0] < b.pos[0];}
bool cmp1(node a , node b){return a.pos[1] < b.pos[1];}
bool cmp2(node a , node b){return a.pos[2] < b.pos[2];}

inline int pushup(int x){
    memcpy(maxP[x] , nd[x].pos , sizeof(nd[x].pos));
    memcpy(minP[x] , nd[x].pos , sizeof(nd[x].pos));
    maxV[x] = nd[x].val;
    for(int p = 0 ; p < 2 ; ++p)
    if(ch[x][p]){
        maxV[x] = max(maxV[x] , maxV[ch[x][p]]);
        for(int i = 0 ; i < 3 ; ++i){
        maxP[x][i] = max(maxP[x][i] , maxP[ch[x][p]][i]);
        minP[x][i] = min(minP[x][i] , minP[ch[x][p]][i]);
        }
    }
    return x;
}

int build(int l , int r , int tp){
    if(l > r) return 0;
    if(l == r) return pushup(l);
    int mid = (l + r) >> 1;
    nth_element(nd + l , nd + mid , nd + r + 1 , tp == 0 ? cmp0 : (tp == 1 ? cmp1 : cmp2));
    ch[mid][0] = build(l , mid - 1 , (tp + 1) % 3);
    ch[mid][1] = build(mid + 1 , r , (tp + 1) % 3);
    return pushup(mid);
}

long long cnt;
void query(int cur , int a , int b){
    if(minP[cur][0] >= a || maxP[cur][2] <= b || minP[cur][1] > b || maxP[cur][1] < a || maxV[cur] <= lastans) return;
    if(maxP[cur][0] < a && minP[cur][2] > b && minP[cur][1] >= a && maxP[cur][1] <= b){
    lastans = maxV[cur]; return;
    }
    if(nd[cur].pos[0] < a && nd[cur].pos[1] >= a && nd[cur].pos[1] <= b && nd[cur].pos[2] > b)
    lastans = max(lastans , nd[cur].val);
    query(ch[cur][0] , a , b); query(ch[cur][1] , a , b);
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    N = read(); M = read();
    for(int i = 1 ; i <= N ; ++i){
    nd[i].pos[1] = i;
    int a = nd[i].val = read();
    nd[i].pos[0] = pre[a]; nd[pre[a]].pos[2] = i;
    pre[a] = i;
    }
    for(int i = 1 ; i <= N ; ++i)
    nd[pre[i]].pos[2] = N + 1;
    int rt = build(1 , N , 0);
    while(M--){
    int x = (read() + lastans) % N + 1 , y = (read() + lastans) % N + 1;
    if(x > y) x ^= y ^= x ^= y;
    lastans = 0;
    query(rt , x , y);
    printf("%d\n" , lastans);
    }
    return 0;
}

BZOJ3489 A simple rmq problem K-D Tree

原文：https://www.cnblogs.com/Itst/p/10502729.html