线段树"/>
bzoj 3489 A simple rmq problem —— 主席树套线段树
题目:.php?id=3489
题解:.html
在我挣扎一下午时 Narh 早就A了...
于是看看有何不同,发现 add 和 insert 中必须把 ls[x] = ls[y] , rs[x] = rs[y] 写在前面,而不能是修改 rs 则在那里单写一个 ls[x] = ls[y] 什么的,否则过不了样例...
然后 find 和 query 中一定要有一个 if(!x) return 0; ,否则秒 WA ...
代码如下:
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define mid ((l+r)>>1) using namespace std; int const xn=1e5+5,xm=xn*20,xy=xm*20; int n,m,cnt,rt[xn],ls[xm],rs[xm],cnt2,rt2[xm],ls2[xy],rs2[xy],lst[xn],mx[xy]; struct N{int pr,nxt,pos,val;}p[xn]; int rd() {int ret=0,f=1; char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=0; ch=getchar();}while(ch>='0'&&ch<='9')ret=(ret<<3)+(ret<<1)+ch-'0',ch=getchar();return f?ret:-ret; } bool cmp(N x,N y){return x.pr<y.pr;} void add(int &x,int y,int l,int r,N t) {x=++cnt2;ls2[x]=ls2[y]; rs2[x]=rs2[y];mx[x]=max(mx[y],t.val);if(l==r)return;if(t.pos<=mid)add(ls2[x],ls2[y],l,mid,t);else add(rs2[x],rs2[x],mid+1,r,t); } void insert(int &x,int y,int l,int r,N t) {x=++cnt;ls[x]=ls[y]; rs[x]=rs[y];add(rt2[x],rt2[y],0,n+1,t);//!!! if(l==r)return;if(t.nxt<=mid)insert(ls[x],ls[y],l,mid,t);else insert(rs[x],rs[y],mid+1,r,t); } int find(int x,int l,int r,int L,int R) {if(!x)return 0;//!!if(l>=L&&r<=R)return mx[x];int ret=0;if(mid>=L)ret=max(ret,find(ls2[x],l,mid,L,R));if(mid<R)ret=max(ret,find(rs2[x],mid+1,r,L,R));return ret; } int query(int x,int l,int r,int L,int R,int ql,int qr) {if(!x)return 0;//!!if(l>=L&&r<=R)return find(rt2[x],0,n+1,ql,qr);int ret=0;if(mid>=L)ret=max(ret,query(ls[x],l,mid,L,R,ql,qr));if(mid<R)ret=max(ret,query(rs[x],mid+1,r,L,R,ql,qr));return ret; } int main() {n=rd(); m=rd();for(int i=1,x;i<=n;i++){x=rd();p[i].pos=i; p[i].val=x;p[i].pr=lst[x]; p[lst[x]].nxt=i;lst[x]=i;}for(int i=1;i<=n;i++)if(!p[i].nxt)p[i].nxt=n+1;sort(p+1,p+n+1,cmp);for(int i=0,t=1;i<=n+1;i++){rt[i]=rt[i-1];while(p[t].pr==i&&t<=n)insert(rt[i],rt[i],0,n+1,p[t++]);}for(int i=1,x,y,l,r,lt=0;i<=m;i++){x=rd(); y=rd();l=min((x+lt)%n+1,(y+lt)%n+1);r=max((x+lt)%n+1,(y+lt)%n+1);lt=query(rt[l-1],0,n+1,r+1,n+1,l,r);// printf("%d\n",lt);}return 0; }
转载于:.html
更多推荐
bzoj 3489 A simple rmq problem —— 主席树套线段树
发布评论