「bzoj3489」A simple rmq problem - K-D树/主席树套主席树 | Bill Yang's Blog

「bzoj3489」A simple rmq problem - K-D树/主席树套主席树

题目大意

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


题目分析

求出每个数出现的前驱$pre$与后继$next$。
题目要求可以转化为:
在满足:

  • $x\in[l,r]$
  • $pre[x]\in(0,l)$
  • $next[x]\in(r,n+1)$

时,询问$x$的最大值。
这是一个三维偏序的关系,若无强制在线操作,可以使用cdq分治。
因为有强制在线,不妨使用K-D树。对范围进行限制并查询范围中最大值点。

当然也可以用主席树套主席树,外部主席树对$pre[]$可持久化,每棵树$root[i]$表示$pre[x]\le i$时的内部信息。
内部主席树对$next[]$可持久化,每棵树$root[i]$表示$next[x]\ge i$时的内部信息;内部主席树的每棵树按照$x$建立下标,维护点权最大值点。

本人仅仅写了K-D树,真是抱歉。


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=100005,K=3;
int D,Left[K],Right[K],ans=0;
struct KD_Tree {
struct Point {
int d[K],Min[K],Max[K];
int ls,rs,val,max;
int& operator [] (int x) {
return d[x];
}
Point(int x=0,int y=0,int z=0,int v=0) {
ls=rs=0;
d[0]=Min[0]=Max[0]=x;
d[1]=Min[1]=Max[1]=y;
d[2]=Min[2]=Max[2]=z;
val=max=v;
}
bool operator < (const Point& b) const {
return d[D]<b.d[D];
}
} p[maxn];
#define lson p[index].ls
#define rson p[index].rs
int build(int Left,int Right,int now) {
int mid=(Left+Right)>>1,root=mid;
D=now;
nth_element(p+Left,p+mid,p+Right+1);
if(Left<mid)p[root].ls=build(Left,mid-1,(now+1)%K);
if(Right>mid)p[root].rs=build(mid+1,Right,(now+1)%K);
push_up(root);
return root;
}
void push_up(int index) {
if(lson)p[index].max=max(p[index].max,p[lson].max);
if(rson)p[index].max=max(p[index].max,p[rson].max);
for(int i=0; i<K; i++) {
if(lson) {
p[index].Min[i]=min(p[index].Min[i],p[lson].Min[i]);
p[index].Max[i]=max(p[index].Max[i],p[lson].Max[i]);
}
if(rson) {
p[index].Min[i]=min(p[index].Min[i],p[rson].Min[i]);
p[index].Max[i]=max(p[index].Max[i],p[rson].Max[i]);
}
}
}
bool inspace(Point p) {
for(int i=0; i<K; i++)
if(p[i]<Left[i]||p[i]>Right[i])return false;
return true;
}
bool check(int index) {
if(!index)return 0;
if(p[index].Max[0]<Left[0]||p[index].Min[0]>Right[0])return 0;
if(p[index].Min[1]>Right[1]||p[index].Max[2]<Left[2])return 0;
return 1;
}
void query(int index) {
if(!index)return;
if(inspace(p[index]))ans=max(ans,p[index].val);
bool lable=check(lson),rable=check(rson);
if(p[lson].max>p[rson].max) {
if(lable&&p[lson].max>=ans)query(lson);
if(rable&&p[rson].max>=ans)query(rson);
} else {
if(rable&&p[rson].max>=ans)query(rson);
if(lable&&p[lson].max>=ans)query(lson);
}
}
} kdtree;
int n,m,lastans=0,a[maxn],Pre[maxn],Next[maxn],Hash[maxn];
int main() {
n=Get_Int();
m=Get_Int();
for(int i=1; i<=n; i++)a[i]=Get_Int();
for(int i=1; i<=n; i++) {
Pre[i]=Hash[a[i]];
Hash[a[i]]=i;
}
for(int i=1; i<=n; i++)Hash[i]=n+1;
for(int i=n; i>=1; i--) {
Next[i]=Hash[a[i]];
Hash[a[i]]=i;
}
for(int i=1; i<=n; i++)kdtree.p[i]=KD_Tree::Point(i,Pre[i],Next[i],a[i]);
int root=kdtree.build(1,n,0);
for(int i=1; i<=m; i++) {
int x=(Get_Int()+lastans)%n+1,y=(Get_Int()+lastans)%n+1;
if(x>y)swap(x,y);
Left[0]=x,Left[1]=0,Left[2]=y+1;
Right[0]=y,Right[1]=x-1,Right[2]=n+1;
ans=0;
kdtree.query(root);
lastans=ans;
printf("%d\n",ans);
}
return 0;
}
0%