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

題解：http://www.itdaan.com/blog/2017/11/24/9bc46b690756fe252e17fc3ca90aa01.html

所以就沒寫KD-tree、樹套堆、分塊，而是寫了樹套樹。

限制條件是：pr<L；nt>R；L<= i <=R。

對pr排序后建主席樹，調用1~L-1的主席樹就能限制好第一個條件；主席樹里維護 nt 的值域，調用R+1~n+1的部分就能限制好第二個條件；因為有第三個條件，所以每個點上帶一個線段樹，維護 i 的位置，記錄max值，就行了。

調了半天原來是讀入理解錯了；1A好高興。

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=1e5+5,M=N*20,M2=M*20; int n,m,tot,tt2,pre[N],rt[N],ans; struct Node{int pr,i,nt,c; }a[N]; struct Tr{int ls,rs,rt; }tr[M]; struct T{int ls,rs,mx; }t[M2]; int rdn() {int ret=0;bool fx=1;char ch=getchar();while(ch>'9'||ch<'0'){if(ch=='-')fx=0;ch=getchar();}while(ch>='0'&&ch<='9') ret=(ret<<3)+(ret<<1)+ch-'0',ch=getchar();return fx?ret:-ret; } bool cmpl(Node u,Node v){return u.pr<v.pr;} void insert(int &cr,int pre,int l,int r,Node k) {cr=++tt2; t[cr].ls=t[pre].ls; t[cr].rs=t[pre].rs;t[cr].mx=max(t[pre].mx,k.c);// printf(" bdin: l=%d r=%d mx=%d\n",l,r,t[cr].mx);if(l==r) return;int mid=l+r>>1;if(k.i<=mid) insert(t[cr].ls,t[pre].ls,l,mid,k);else insert(t[cr].rs,t[pre].rs,mid+1,r,k); } void build(int &cr,int pre,int l,int r,Node k) {cr=++tot; tr[cr].ls=tr[pre].ls; tr[cr].rs=tr[pre].rs;insert(tr[cr].rt,tr[pre].rt,1,n,k); // printf("bdout: l=%d r=%d rt=%d\n",l,r,tr[cr].rt);if(l==r) return; int mid=l+r>>1;if(k.nt<=mid) build(tr[cr].ls,tr[pre].ls,l,mid,k);else build(tr[cr].rs,tr[pre].rs,mid+1,r,k); } int find(int x) {int l=1,r=n,ret=0;while(l<=r){int mid=l+r>>1;if(a[mid].pr<=x)ret=mid,l=mid+1;else r=mid-1;}return ret; } int query(int cr,int l,int r,int L,int R) {if(!cr) return 0; // printf(" qin: l=%d r=%d(L=%d R=%d)\n",l,r,L,R);if(l>=L&&r<=R) return t[cr].mx;int mid=l+r>>1,ret=0;if(L<=mid) ret=query(t[cr].ls,l,mid,L,R);if(mid<R) ret=max(ret,query(t[cr].rs,mid+1,r,L,R)); // printf(" qin: l=%d r=%d ret=%d\n",l,r,ret);return ret; } int query(int cr,int l,int r,int L,int R,int ql,int qr) {if(!cr)return 0; // printf("qout: l=%d r=%d rt=%d(L=%d R=%d)\n", // l,r,tr[cr].rt,L,R);if(l>=L&&r<=R) return query(tr[cr].rt,1,n,ql,qr);int mid=l+r>>1,ret=0;if(L<=mid) ret=query(tr[cr].ls,l,mid,L,R,ql,qr);if(mid<R) ret=max(ret,query(tr[cr].rs,mid+1,r,L,R,ql,qr)); // printf("qout: l=%d r=%d ret=%d\n",l,r,ret);return ret; } int main() {n=rdn(); m=rdn();for(int i=1,d;i<=n;i++){d=rdn(); a[i].pr=pre[d];a[i].i=i; a[i].c=d; pre[d]=i;}for(int i=1;i<=n;i++) pre[i]=n+1;for(int i=n;i;i--)a[i].nt=pre[a[i].c],pre[a[i].c]=i;sort(a+1,a+n+1,cmpl);for(int i=1;i<=n;i++)build(rt[i],rt[i-1],1,n+1,a[i]);for(int i=1,l,r,x,y,k;i<=m;i++){x=rdn(); y=rdn();l=min((x+ans)%n+1,(y+ans)%n+1);r=max((x+ans)%n+1,(y+ans)%n+1);k=find(l-1);// printf("st: l=%d r=%d k=%d\n",l,r,k); ans=query(rt[k],1,n+1,r+1,n+1,l,r);printf("%d\n",ans);}return 0; }

?

轉載于:https://www.cnblogs.com/Narh/p/9719242.html

總結

以上是生活随笔為你收集整理的bzoj 3489 A simple rmq problem——主席树套线段树的全部內容，希望文章能夠幫你解決所遇到的問題。

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