BZOJ 3489 A simple rmq problem 可持久化KDtree/二维线段树

题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=3489

题意概述：

给出一个序列，每次询问一个序列区间中仅出现了一次的数字最大是多少，如果没有的话输出0。

N<=100000,M<=200000.

分析：

考试的时候YY了一个可持久化KDtree可惜没有打完（一开始想着一维做最后发现自己真是太天真了hahahaha），最后把它改对了。

把两种方法都介绍一下：

持久化KDtree：

首先我们令last[i]表示A[i]在i的左边最靠右的出现位置，那么显然对于询问[l,r]，如果我们当前计算出的last是基于[1,r]的数据的，那么我们要找的实际上是(last[A[i]],i]中包含l的最大的A[i]，转化一下就变成了last[A[i]]<l<=i，如果我们把它做成平面上的点(i,last[A[i]])，权值为A[i]，并且序列中每个值仅有最后一次出现的位置对应的i做成的点有值，我们每一次询问[l,r]实际上询问的是基于[1,r]中的信息做成的点在平面范围{ (x,y) | x>=i,y<l }的点中的最大权值，这可以用KDtree来做。

因此我们只要先把所有的点预处理出来建成KDtree，修改的时候可持久化一下就可以了。（如果您执意认为三维KDtree更好的话我只能说它太容易被卡啦......）

期望时间复杂度O((N+M)sqrt(N))

二维线段树：

我们令Last[i]表示i左边第一个和i权值相同的点的下标（没有的话为0），Next[i]表示i右边第一个和i权值相同的点的下标（没有的话为N+1），那么对于询问[l,r]满足Last[i]<l<=i,i<=r<Next[i]来说，A[i]就可能成为它的解，可以发现我们把l当成平面的横坐标，r当成平面的纵坐标，i可以影响到的区域正好是平面上的一个矩形！因此只要用二维线段树动态开点+标记永久化就可以做了。

时间复杂度O(M*logN^2)

这两种做法的话，随机数据KDtree0.4s+吊打二维线段树2.8s+，而把询问构造成几乎全部接近于单点询问的时候KDtree到了极限大概3.6s的样子，这个时候二维线段树很开心1.8s+，三维KDtree就更不要说了5s+......（4s的时限干不死我的KDtreehahahahahaha如果您卡掉了我请不要怼我）

最后，我发现数据结构这种东西不同结构体写常数会小一些，尤其是当需要卡极限的时候不写在结构体里面效果就很显著......还有为什么把变量ans当成参数带到query里面去居然变快了？！是引用地址的原因吗......

论常数优化的重要性！

KDtree：

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cstdlib>
  5 #include<algorithm>
  6 #include<cmath>
  7 #include<queue>
  8 #include<set>
  9 #include<map>
 10 #include<vector>
 11 #include<cctype>
 12 #define inf (1e8+5)
 13 using namespace std;
 14 const int MAXN=100005;
 15 const int maxn=5000005;
 16 const int maxm=100005;
 17 
 18 int N,M,A[MAXN],last[MAXN],cnt,D;
 19 struct XY{
 20     int d[2];
 21     friend bool operator < (XY a,XY b){
 22         return a.d[D]<b.d[D];
 23     }
 24     friend bool operator == (XY a,XY b){
 25         return a.d[0]==b.d[0]&&a.d[1]==b.d[1];
 26     }
 27 }p[MAXN],pp[MAXN],node[maxn],mn[maxn],mx[maxn];
 28 int root[maxm],np,lc[maxn],rc[maxn],maxv[maxn],w[maxn],ver[maxn];
 29 int copynode(int p,int t){
 30     np++,maxv[np]=maxv[p],w[np]=w[p];
 31     lc[np]=lc[p],rc[np]=rc[p],ver[np]=t;
 32     node[np]=node[p],mx[np]=mx[p],mn[np]=mn[p];
 33     return np;
 34 }
 35 void pushup1(int now){
 36     for(int i=0;i<2;i++){
 37         mn[now].d[i]=min(node[now].d[i],min(mn[lc[now]].d[i],mn[rc[now]].d[i]));
 38         mx[now].d[i]=max(node[now].d[i],max(mx[lc[now]].d[i],mx[rc[now]].d[i]));
 39     }
 40 }
 41 void pushup2(int now){
 42     maxv[now]=max(w[now],max(maxv[lc[now]],maxv[rc[now]]));
 43 }
 44 void build(int &now,int L,int R,XY *a,int k){
 45     if(L>R) return;
 46     now=++np,lc[now]=rc[now]=0;
 47     int m=L+R>>1; D=k;
 48     nth_element(a+L,a+m,a+R+1);
 49     node[now]=mx[now]=mn[now]=a[m];
 50     maxv[now]=w[now]=0;
 51     build(lc[now],L,m-1,a,k^1);
 52     build(rc[now],m+1,R,a,k^1);
 53     pushup1(now);
 54 }
 55 bool isoutside(XY p,int now){
 56     return p.d[0]<mn[now].d[0]||p.d[0]>mx[now].d[0]
 57         ||p.d[1]<mn[now].d[1]||p.d[1]>mx[now].d[1];
 58 }
 59 int update(int now,XY p,int v,int t){
 60     if(!now) return 0;
 61     if(isoutside(p,now)) return 0;
 62     if(node[now]==p){
 63         if(ver[now]!=t) now=copynode(now,t);
 64         w[now]=v; pushup2(now);
 65         return now;
 66     }
 67     int re=0;
 68     if(re=update(lc[now],p,v,t)){
 69         if(ver[now]!=t) now=copynode(now,t);
 70         lc[now]=re; pushup2(now);
 71         return now;
 72     }
 73     if(re=update(rc[now],p,v,t)){
 74         if(ver[now]!=t) now=copynode(now,t);
 75         rc[now]=re; pushup2(now);
 76         return now;
 77     }
 78     return 0;
 79 }
 80 void query(int now,int l,int &ret){
 81     if(mx[now].d[0]<l||mn[now].d[1]>=l) return;
 82     if(mn[now].d[0]>=l&&mx[now].d[1]<l){
 83         if(maxv[now]>ret) ret=maxv[now];
 84         return;
 85     }
 86     if(node[now].d[0]>=l&&node[now].d[1]<l&&w[now]>ret) ret=w[now];
 87     if(maxv[lc[now]]>ret) query(lc[now],l,ret);
 88     if(maxv[rc[now]]>ret) query(rc[now],l,ret);
 89 }
 90 
 91 void _scanf(int &x)
 92 {
 93     x=0;
 94     char ch=getchar();
 95     while(ch<'0'||ch>'9') ch=getchar();
 96     while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
 97 }
 98 int out_cnt; char out[15];
 99 void _printf(int x)
100 {
101     out[++out_cnt]=x%10+'0',x/=10;
102     while(x) out[++out_cnt]=x%10+'0',x/=10;
103     while(out_cnt) putchar(out[out_cnt--]);
104     putchar('
');
105 }
106 void data_in()
107 {
108     _scanf(N);_scanf(M);
109     for(int i=1;i<=N;i++) _scanf(A[i]);
110     for(int i=1;i<=N;i++){
111         p[i].d[0]=i,p[i].d[1]=last[A[i]];
112         last[A[i]]=i;
113     }
114     for(int i=1;i<=N;i++) pp[i]=p[i];
115     mx[0].d[0]=mx[0].d[1]=0,mn[0].d[0]=mn[0].d[1]=inf;
116     build(root[0],1,N,p,0);
117     for(int i=1;i<=N;i++){
118         root[i]=root[i-1];
119         if(pp[i].d[1]) root[i]=update(root[i],pp[pp[i].d[1]],0,i);
120         root[i]=update(root[i],pp[i],A[i],i);
121     }
122 }
123 void work()
124 {
125     int l,r,x,y,ans;
126     for(int i=1;i<=M;i++){
127         _scanf(x);_scanf(y);
128         l=min((x+ans)%N+1,(y+ans)%N+1);
129         r=max((x+ans)%N+1,(y+ans)%N+1);
130         ans=0; query(root[r],l,ans);
131         _printf(ans);
132     }
133 }
134 int main()
135 {
136     data_in();
137     work();
138     return 0;
139 }

View Code

二维线段树：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<algorithm>
 6 #include<cmath>
 7 #include<queue>
 8 #include<set>
 9 #include<map>
10 #include<vector>
11 #include<cctype>
12 using namespace std;
13 const int maxn=100005;
14 const int maxnode=30000005;
15 
16 int N,M,a[maxn],Last[maxn],Next[maxn],last[maxn];
17 int root,np,rt[maxnode],lc[maxnode],rc[maxnode],mx[maxnode];
18 void inupdate(int &now,int L,int R,int A,int B,int v){
19     if(!now) now=++np;
20     if(A<=L&&R<=B){
21         if(v>mx[now]) mx[now]=v;
22         return;
23     }
24     int m=L+R>>1;
25     if(B<=m) inupdate(lc[now],L,m,A,B,v);
26     else if(A>m) inupdate(rc[now],m+1,R,A,B,v);
27     else inupdate(lc[now],L,m,A,B,v),inupdate(rc[now],m+1,R,A,B,v);
28 }
29 int inquery(int now,int L,int R,int p){
30     if(!now) return 0;
31     if(L==R) return mx[now];
32     int m=L+R>>1;
33     if(p<=m) return max(mx[now],inquery(lc[now],L,m,p));
34     return max(mx[now],inquery(rc[now],m+1,R,p));
35 }
36 void update(int &now,int L,int R,int A,int B,int AA,int BB,int v){
37     if(!now) now=++np;
38     if(A<=L&&R<=B){
39         inupdate(rt[now],1,N,AA,BB,v);
40         return;
41     }
42     int m=L+R>>1;
43     if(B<=m) update(lc[now],L,m,A,B,AA,BB,v);
44     else if(A>m) update(rc[now],m+1,R,A,B,AA,BB,v);
45     else update(lc[now],L,m,A,B,AA,BB,v),update(rc[now],m+1,R,A,B,AA,BB,v);
46 }
47 int query(int now,int L,int R,int p1,int p2){
48     if(!now) return 0;
49     if(L==R) return inquery(rt[now],1,N,p2);
50     int m=L+R>>1;
51     int re=inquery(rt[now],1,N,p2);
52     if(p1<=m) return max(re,query(lc[now],L,m,p1,p2));
53     return max(re,query(rc[now],m+1,R,p1,p2));
54 }
55 
56 void _scanf(int &x)
57 {
58     x=0;
59     char ch=getchar();
60     while(ch<'0'||ch>'9') ch=getchar();
61     while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
62 }
63 int out_cnt; char out[15];
64 void _printf(int x)
65 {
66     out[++out_cnt]=x%10+'0',x/=10;
67     while(x) out[++out_cnt]=x%10+'0',x/=10;
68     while(out_cnt) putchar(out[out_cnt--]);
69     putchar('
');
70 }
71 void data_in()
72 {
73     _scanf(N);_scanf(M);
74     for(int i=1;i<=N;i++) _scanf(a[i]);
75     for(int i=1;i<=N;i++)
76         Last[i]=last[a[i]],last[a[i]]=i;
77     for(int i=1;i<=N;i++) last[i]=N+1;
78     for(int i=N;i>=1;i--)
79         Next[i]=last[a[i]],last[a[i]]=i;
80     for(int i=1;i<=N;i++)
81         update(root,1,N,Last[i]+1,i,i,Next[i]-1,a[i]);
82 }
83 void work()
84 {
85     int x,y,l,r,ans=0;
86     for(int i=1;i<=M;i++){
87         _scanf(x);_scanf(y);
88         l=min((x+ans)%N+1,(y+ans)%N+1);
89         r=max((x+ans)%N+1,(y+ans)%N+1);
90         ans=query(root,1,N,l,r);
91         _printf(ans);
92     }
93 }
94 int main()
95 {
96     data_in();
97     work();
98     return 0;
99 }

View Code