标准无脑数据结构题?

一眼看过去有一种数据结构嵌套的冲动。 然后发现就是可以数据结构嵌套, 还需要可持久化。。

然后, 发现可以用“暴力”(KD-tree)艹掉?

传送门

题目大意

给出一个长度为\(n\)的序列,给出\(M\)个询问:在\([l,r]\)之间找到一个在这个区间里只出现过一次的数,并且要求找的这个数尽可能大。如果找不到这样的数,则直接输出0。强制在线。

解题报告

题目中的在\([l,r]\)中只出现一次的意思, 是前一个在\([0,l-1]\), 后一个在\([r+1,n+1]\), 自己在\([l,r]\)的意思。

显然可以线性预处理前一个和后一个的位置, 记为\(l_x, n_x\).

那就是要查询\(l_x \in [0, l-1], n_x \in [r+1,n+1], x \in [l,r]\)的最大值

  • 解法一

可以将\(l_x\)可持久化, 然后\(n_x\)嵌套\(x\), 做一个可持久化线段树套线段树。

时间复杂度\(O(n \log^2 n)\)

空间复杂度不知道, 反正巨卡但是能过。

  • 解法二

相当于一个三维空间的空间最大点问题。

这个可以用KD-tree暴力的做。

复杂度是\(O(n^{\frac{5}{3}})\)

但是跑得更快。

代码

  • 树套树(可持久化)
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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
#define rep(i,a,b) for(int i=int(a),nn=int(b);i<=nn;++i)
#define vep(i,a,b) for(int i=int(a),nn=int(b);i>=nn;--i)
#define xep(i,b) for(int i=0,nn=int(b);i<nn;++i)
#define mp make_pair
#define x first
#define y second
typedef pair<int,int> pii;
const int N=100010;
int sn[40000000][2],rt[N],v[40000000],ts;
int a[N], ls[N], nx[N], co[N], las,n,m;
struct info {
int l,r,x,v; info(int l=0,int r=0,int x=0,int v=0)
:l(l),r(r),x(x),v(v) {}
} p[N];
inline void in(int &x) {
char c=getchar(); int f=1;
for (; c<'0'||c>'9';c=getchar()) f=(c=='-')?-1:f;
for (x=0; c>='0'&&c<='9';c=getchar()) x=x*10+c-48;
x*=f;
}
inline void cmax(int &x,int a) { x=(a>x?a:x); }
void inmo(int &x,int fm,int l,int r,int w,int va) {
x=++ts; memcpy(sn[x],sn[fm],sizeof(sn[fm])),v[x]=v[fm];
cmax(v[x], va); if (l==r) return; int md=(l+r)>>1;
if (w<=md) inmo(sn[x][0],sn[fm][0],l,md,w,va);
else inmo(sn[x][1],sn[fm][1],md+1,r,w,va);
}
void outmo(int &x,int fm,int l,int r,info p) {
x=++ts; memcpy(sn[x],sn[fm],sizeof(sn[fm])),v[x]=v[fm];
inmo(v[x],v[fm],1,n,p.x,p.v);
if (l==r) return; int md=(l+r)>>1;
if (p.r<=md) outmo(sn[x][0],sn[fm][0],l,md,p);
else outmo(sn[x][1],sn[fm][1],md+1,r,p);
}
int inqy(int x,int l,int r,pii p) {
int mx=0; if (!x) return mx;
if (p.x<=l&&r<=p.y) return v[x];
int md=(l+r)>>1;
if (p.x<=md) cmax(mx,inqy(sn[x][0],l,md,p));
if (p.y>md) cmax(mx,inqy(sn[x][1],md+1,r,p));
return mx;
}
int outqy(int x,int l,int r,pii p) {
int mx=0; if (!x) return mx;
if (p.y+1<=l&&r<=n+1) { cmax(mx,inqy(v[x],1,n,p)); return mx;}
int md=(l+r)>>1;
if (p.y+1<=md) cmax(mx,outqy(sn[x][0],l,md,p));
if (n+1>md) cmax(mx,outqy(sn[x][1],md+1,r,p));
return mx;
}
inline bool cmp(info a, info b) { return a.l<b.l; }
int main() {
int l,r; in(n),in(m);
rep(i,1,n) in(a[i]), ls[i]=co[a[i]], nx[co[a[i]]]=i, co[a[i]]=i;
rep(i,1,n) nx[i]=(nx[i]?nx[i]:n+1), p[i]=info(ls[i],nx[i],i,a[i]);
sort(p+1, p+1+n, cmp);
int j=1; xep(i, n) {
rt[i]=(i?rt[i-1]:0);
while (j<=n&&p[j].l==i)
outmo(rt[i],rt[i],2,n+1,p[j]), ++j;
}
while (m--) {
in(l), in(r), l=(l+las)%n+1, r=(r+las)%n+1; if(l>r) swap(l,r);
printf("%d\n", las=outqy(rt[l-1],2,n+1,mp(l,r)));
}
return 0;
}
  • KD-tree
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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
using namespace std;
#define rep(i,a,b) for(int i=int(a),nn=int(b);i<=nn;++i)
#define vep(i,a,b) for(int i=int(a),nn=int(b);i>=nn;--i)
#define xep(i,b) for(int i=0,nn=int(b);i<nn;++i)
const int N=100100;
int di, n,m,a[N],ls[N],nx[N],co[N],las;
struct node {
int mn[3],mx[3],d[3],l,r,v,as;
} v[N];
struct ques {
int mn[3],mx[3]; ques() {} ques(int l,int r) {
mn[0]=0,mx[0]=l-1,mn[1]=r+1,mx[1]=n+1,mn[2]=l,mx[2]=r;
}
} qs;
inline void in(int &x) {
char c=getchar(); int f=1;
for (;c<'0'||c>'9';c=getchar()) f=(c=='-'?-1:f);
for (x=0;c>='0'&&c<='9';c=getchar()) x=x*10+c-48;
x*=f;
}
inline void cmx(int &x,int a) { x=(a>x?a:x); }
inline void cmn(int &x,int a) { x=(a<x?a:x); }
inline bool cmp(node a, node b) { return a.d[di]<b.d[di]; }
inline void push(int x) { int y;
if (y=v[x].l) { xep(i,3) cmn(v[x].mn[i],v[y].mn[i]), cmx(v[x].mx[i],v[y].mx[i]); cmx(v[x].as,v[y].as);}
if (y=v[x].r) { xep(i,3) cmn(v[x].mn[i],v[y].mn[i]), cmx(v[x].mx[i],v[y].mx[i]); cmx(v[x].as,v[y].as);}
}
int build(int l,int r,int d) {
di=d; int md=(l+r)>>1; nth_element(v+l,v+md,v+r+1,cmp);
xep(i,3) v[md].mn[i]=v[md].mx[i]=v[md].d[i];
v[md].as=v[md].v;
if (md!=l) v[md].l=build(l,md-1,(d+1)%3);
if (md!=r) v[md].r=build(md+1,r,(d+1)%3);
push(md); return md;
}
inline bool enough(node &v) {
bool may=1; xep(i,3) if (qs.mn[i]>v.mn[i]||v.mx[i]>qs.mx[i]) return 0;
return 1;
}
inline bool illegal(node &v) {
xep(i,3) if (v.mn[i]>qs.mx[i]||v.mx[i]<qs.mn[i]) return 1;
return 0;
}
inline bool legal(node &v) {
xep(i,3) if (v.d[i]<qs.mn[i]||v.d[i]>qs.mx[i]) return 0;
return 1;
}
inline int count(node &v) {
if (illegal(v)) return 0; else return v.as;
}
void query(int x,int d) {
di=d; int l=0, la=0, r=0, ra=0;
if (enough(v[x])) cmx(las,v[x].as);
if (legal(v[x])) cmx(las, v[x].v);
if (l=v[x].l) la=count(v[l]);
if (r=v[x].r) ra=count(v[r]);
if (la<ra) swap(la,ra), swap(l,r);
if (la>las) query(l,(d+1)%3);
if (ra>las) query(r,(d+1)%3);
}
int main() {
in(n),in(m); rep(i,1,n) in(a[i]); int l, r;
rep(i,1,n) ls[i]=co[a[i]], nx[co[a[i]]]=i, co[a[i]]=i;
rep(i,1,n) {
nx[i]=(nx[i]?nx[i]:n+1);
v[i].d[0]=ls[i],v[i].d[1]=nx[i],v[i].d[2]=i,v[i].v=a[i];
}
int rt=build(1,n,0);
while (m--) {
in(l),in(r),l=(l+las)%n+1, r=(r+las)%n+1; if (l>r) swap(l,r);
qs=ques(l,r),las=0,query(rt,0), printf("%d\n", las);
}
return 0;
}

留言