https://www.zybuluo.com/ysner/note/1298153

題面

給出一個長度為\(n\)的序列，給出\(M\)個詢問：
在\([l,r]\)之間找到一個在這個區間里只出現過一次的數，并且要求找的這個數盡可能大。
如果找不到這樣的數，則直接輸出\(0\)。我會采取一些措施強制在線。

• \(n\leq10^5,m\leq2*10^5,a_i\leq n\)

  解析

  只出現過一次，就是上一次出現在位置\(l\)之前，下一次出現在位置\(r\)之后。
  這個有點像三維偏序，但這里有一維是區間啊。
  樹套樹續一下應該能過。

然而，對于維數較高的范圍計數問題，\(kd-tree\)是更佳選擇。
其復雜度穩定\(O(kn^{1-\frac{1}{k}})\)（\(k\)為維數），而且空間線性。

一般框架：

• 如果當前節點存的點被詢問范圍包括,用這個點貢獻答案
• 如果當前節點的范圍完全被詢問范圍包括,直接用整個節點貢獻答案
• 如果當前節點的范圍(一個超立方體)和詢問范圍沒有交,返回
• 否則,遞歸進入左右兒子

對一個新加入的點，先自己更新自己的范圍，再用兒子更新自己的范圍。

把上一次，這一次，下一次這個數出現的位置看作三個維度就可以了。

#include<iostream> #include<cmath> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #define ll long long #define re register #define il inline #define ls t[k].l #define rs t[k].r #define fp(i,a,b) for(re int i=a;i<=b;i++) #define fq(i,a,b) for(re int i=a;i>=b;i--) using namespace std; const int N=2e5+100; int n,m,b[N],R[N],L[N],now,app[N],rt,ans; il ll gi() {re ll x=0,t=1;re char ch=getchar();while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();if(ch=='-') t=-1,ch=getchar();while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();return x*t; } il void cmin(re int &x,re int y){x=min(x,y);} il void cmax(re int &x,re int y){x=max(x,y);} struct dat {int d[3],w,max;il bool operator < (const dat &o) const{return d[now]<o.d[now];} }a[N]; struct node {dat a;int l,r,mn[3],mx[3]; }t[N]; struct kd_tree {il void upd(re int k,re int p){fp(i,0,2) cmin(t[k].mn[i],t[p].mn[i]),cmax(t[k].mx[i],t[p].mx[i]);t[k].a.max=max(t[k].a.max,t[p].a.max);}il void pushup(re int k){fp(i,0,2) t[k].mn[i]=t[k].mx[i]=t[k].a.d[i];if(ls) upd(k,ls);if(rs) upd(k,rs);}il void Build(re int &k,re int l,re int r,re int tag){re int mid=l+r>>1;now=tag;nth_element(a+l,a+mid,a+r+1);k=mid;t[k].a=a[mid];if(l<mid) Build(ls,l,mid-1,(tag+1)%3);else ls=0;if(mid<r) Build(rs,mid+1,r,(tag+2)%3);else rs=0;pushup(k);}il void Query(re int k,re int l,re int r){if(!k||t[k].a.max<ans) return;if(t[k].a.d[1]>=l&&t[k].a.d[1]<=r&&t[k].a.d[0]<l&&t[k].a.d[2]>r) ans=max(ans,t[k].a.w);if(t[k].mn[1]>=l&&t[k].mx[1]<=r&&t[k].mx[0]<l&&t[k].mn[2]>r) ans=max(ans,t[k].a.max);if(t[k].mn[1]>r||t[k].mx[1]<l||t[k].mn[0]>=l||t[k].mx[2]<=r) return;Query(ls,l,r);Query(rs,l,r);} }kd; int main() {n=gi();m=gi();fp(i,1,n) b[i]=gi(),L[i]=app[b[i]],app[b[i]]=i,R[i]=n+1;fp(i,0,n) app[i]=n+1;fq(i,n,1) R[i]=app[b[i]],app[b[i]]=i;fp(i,1,n) a[i].d[0]=L[i],a[i].d[1]=i,a[i].d[2]=R[i],a[i].max=a[i].w=b[i];kd.Build(rt,1,n,0);while(m--){re int l=gi(),r=gi();l=(l+ans)%n+1,r=(r+ans)%n+1;if(l>r) swap(l,r);ans=0;kd.Query(rt,l,r);printf("%d\n",ans);}return 0; }

轉載于:https://www.cnblogs.com/yanshannan/p/9727305.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

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

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