A simple rmq problem

題目大意：給定一個長度為$n$的序列，給出$m$個詢問：在$[l,r]$之間找到一個在這個區間里只出現過一次的最大的數。

注釋：$1\le n\le 10^5$，$1\le mle 2\cdot 10^5$。

---

想法：

我的第一想法是莫隊。

結果發現是強制在線（離線我也不會...

想了想其實$KD-Tree$還是比較顯然的。

我們設$l_i$表示$a_i$上一次出現的位置，$r_i$表示下一次。

緊接著我們把第$i$個數轉化為三維坐標軸上的點$(l_i,i,r_i)$。

用$KD-Tree$維護直接查即可。

Code：

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #define N 100010 using namespace std; int v[N],lst[N],dic[N],nxt[N],d,l,r,ans,rt; char *p1,*p2,buf[100000]; #define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++) int rd() {int x=0,f=1; char c=nc(); while(c<48) {if(c=='-') f=-1; c=nc();} while(c>47) x=(((x<<2)+x)<<1)+(c^48),c=nc(); return x*f;} inline void Max(int &x,int y) {x=x>y?x:y;} inline void Min(int &x,int y) {x=x<y?x:y;} struct Node {int p[3],mx[3],mn[3],ans,size,val,ls,rs;}a[N]; inline bool cmp(const Node &a,const Node &b) {for(int i=0;i<3;i++) if(a.p[(d+i)%3]!=b.p[(d+i)%3]) return a.p[(d+i)%3]<b.p[(d+i)%3];return true; } inline void pushup(int x,int k) {a[x].size+=a[k].size;for(int i=0;i<3;i++) Max(a[x].mx[i],a[k].mx[i]),Min(a[x].mn[i],a[k].mn[i]);Max(a[x].ans,a[k].ans); } int build(int l,int r,int now) {int mid=(l+r)>>1;d=now; nth_element(a+l,a+mid,a+r+1,cmp);for(int i=0;i<3;i++) a[mid].mx[i]=a[mid].mn[i]=a[mid].p[i];a[mid].ans=a[mid].val;if(l<mid) a[mid].ls=build(l,mid-1,(now+1)%3),pushup(mid,a[mid].ls);if(mid<r) a[mid].rs=build(mid+1,r,(now+1)%3),pushup(mid,a[mid].rs);return mid; } bool judge(int x) {return a[x].ans>ans&&a[x].mx[0]>=l&&a[x].mn[0]<=r&&a[x].mn[1]<l&&a[x].mx[2]>r; } void query(int x) {if(!x||!judge(x)) return;if(a[x].p[0]>=l&&a[x].p[0]<=r&&a[x].p[1]<l&&a[x].p[2]>r) Max(ans,a[x].val);query(a[x].ls); query(a[x].rs); } int main() {int n=rd(),m=rd();for(int i=1;i<=n;i++) v[i]=rd(),lst[i]=dic[v[i]],nxt[dic[v[i]]]=i,dic[v[i]]=i;for(int i=1;i<=n;i++) a[i].p[0]=i,a[i].p[1]=lst[i],a[i].p[2]=nxt[i]?nxt[i]:n+1,a[i].val=v[i];rt=build(1,n,0); while(m--){l=(rd()+ans)%n+1,r=(rd()+ans)%n+1; if(l>r) swap(l,r);ans=0,query(rt); printf("%d\n",ans);}return 0; }

小結：$KD-Tree$雖然是一個暴力，但是它的思想還是非常不錯的。

轉載于:https://www.cnblogs.com/ShuraK/p/10243973.html

總結

以上是生活随笔為你收集整理的[bzoj3489]A simple rmq problem_KD-Tree的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。