题目链接

题意

输入一个长度为 $n$ 的序列 接着处理 $m$ 次在线询问。每组询问给出 $l,r$ ，要求你找出 $[l,r]$ 中只出现过一次的数的最大值，如果没有输出 $0$。

$n \leq 10^5,m \leq 2 \times 10^5$

题解

套路般地处理出 $pre_i$ 和 $suf_i$ 表示上一个和下一个和它值相同的位置。一次询问相当于是询问 $i \in [l,r],pre_i < l,suf_i > r$ 的点的最大值。

显然这个问题可以用两个主席树嵌套解决 但是这样并不好。

我们考虑这其实是一个在三维空间里的某个立方体内的信息 所以可以用 KDTree 维护

时间复杂度 $O(n^{\frac{5}{3}})$

为什么写这个博客呢？主要是发现自己 KDTree 写的全是 BUG。

1. KDTree询问的时候要统计到达的每一个点 并不是像线段树那样定位每个区间就好了。
2. KDTree询问的时候需要剪枝 维护一个全局变量
3. 好像也没了。。。就是自己太菜了

const int MAXN = 200000+5;
int dir;
struct Node{
    int pos[3],val;    
    
    bool operator < (const Node &t) const {
        return pos[dir] < t.pos[dir];
    }
}v[MAXN];

int mx[MAXN][3],mn[MAXN][3],sm[MAXN];
int ch[MAXN][2];
#define lc (ch[x][0])
#define rc (ch[x][1])

inline void pushup(int x){
    sm[x] = v[x].val;//DEBUG(sm[x]);
    FOR(i,0,2) mx[x][i] = mn[x][i] = v[x].pos[i];
    FOR(i,0,1){
        int p = ch[x][i];
        if(p){
            FOR(i,0,2) mx[x][i] = std::max(mx[x][i],mx[p][i]),
            mn[x][i] = std::min(mn[x][i],mn[p][i]);
            sm[x] = std::max(sm[x],sm[p]);
        }
    }
}

inline int build(int l,int r,int dir){
    ::dir = dir;
    if(l > r) return 0;
    if(l == r){pushup(l);return l;}
    int mid = (l + r) >> 1;
    std::nth_element(v+l,v+mid,v+r+1);
    ch[mid][0] = build(l,mid-1,(dir+1)%3);
    ch[mid][1] = build(mid+1,r,(dir+1)%3);
    pushup(mid);return mid;
}
// (i,pre[i],suf[i])
int ans;// kdtree 剪枝必备
inline void query(int x,int l,int r){
//    DEBUG(x);
    if(!x) return;
    if(mx[x][0] < l || mn[x][0] > r || mn[x][1] >= l || mx[x][2] <= r || sm[x] <= ans) return;
    if(mn[x][0] >= l && mx[x][0] <= r && mx[x][1] < l && mn[x][2] > r)
        {ans = std::max(ans,sm[x]);return;}
    if(v[x].pos[0] >= l && v[x].pos[0] <= r && v[x].pos[1] < l && v[x].pos[2] > r)
        ans = std::max(ans,v[x].val);// 注意统计每个点
    query(lc,l,r);query(rc,l,r);
}
int a[MAXN],pre[MAXN],suf[MAXN],t[MAXN];
int main(){
    int n,m;scanf("%d%d",&n,&m);
    FOR(i,1,n){
        scanf("%d",a+i);
        pre[i] = t[a[i]];t[a[i]] = i;
    }
    std::fill(t,t+n+1,n+1);
    ROF(i,n,1) suf[i] = t[a[i]],t[a[i]] = i;
    FOR(i,1,n) v[i].pos[0] = i,v[i].pos[1] = pre[i],v[i].pos[2] = suf[i],v[i].val = a[i];
    int rt = build(1,n,0);
    FOR(i,1,m){
        int l,r;scanf("%d%d",&l,&r);
        l = (l+ans)%n+1;r = (r+ans)%n+1;
        if(l > r) std::swap(l,r);
        ans = 0;query(rt,l,r);
        printf("%d\n",ans);
    }
    return 0;
}