广州建网站的网络公司,网站开发费用怎么入账,网站管理系统设置,国外网站建设软件排行榜BZOJ3489 A simple rmq problem Description 因为是OJ上的题#xff0c;就简单点好了。给出一个长度为n的序列#xff0c;给出M个询问#xff1a;在[l,r]之间找到一个在这个区间里只出现过一次的数#xff0c;并且要求找的这个数尽可能大。如果找不到这样的数#xff0c;则… BZOJ3489 A simple rmq problem Description 因为是OJ上的题就简单点好了。给出一个长度为n的序列给出M个询问在[l,r]之间找到一个在这个区间里只出现过一次的数并且要求找的这个数尽可能大。如果找不到这样的数则直接输出0。我会采取一些措施强制在线。 Input 第一行为两个整数N,M。M是询问数N是序列的长度N100000M200000) 第二行为N个整数描述这个序列{ai}其中所有1aiN 再下面M行每行两个整数xy 询问区间[l,r]由下列规则产生OIER都知道是怎样的吧_) lmin(xlastans)mod n1,(ylastansmod n1); rmax(xlastans)mod n1,(ylastansmod n1); Lastans表示上一个询问的答案一开始lastans为0 Output 一共M行每行给出每个询问的答案。 Sample Input 10 10 6 4 9 10 9 10 9 4 10 4 3 8 10 1 3 4 9 4 8 1 7 8 2 9 1 1 7 3 9 9 Sample Output 4 10 10 0 0 10 0 4 0 4 还是吐槽一下BZOJ的土豆(评测机)什么数组开小了显示WA数组开大一点就CE这可真是友好请问RE呢MLE呢 然后讲讲这题思路 一开始看到以为是树套树套树 蒙圈了 想了⑩分钟无果然后就去看题解 结果发现可以用排序的方法把三维降成两维 只不过嘛。需要可持久化 不过我们不虚 可持久化树套树不就是在可持久化线段树上多加一句插入吗理直气壮 首先我们考虑一个数在区间内出现一次的充要条件是什么 1.lposir1.lposir 2.lprei2.lprei 3.rnxti3.rnxti 其中pos表示位置pre和nxt分别表示上一个和下一个这个数出现的位置 很妙啊 我们考虑以pre为键值排序 然后我们发现我们查询的区间变成了一个前缀 所以就将pre可持久化一下 然后我们又发现nxt也是我们的限制条件 所以我们在外层的树上以nxt为下标所以查询就变成了在线段树上查询后缀 但是还有pos的限制怎么办 所以就把内层树搞成原序列的位置就好了 然后查询的时候非常套路地二分一下pre的位置剩下的该怎么查怎么查 #includebits/stdc.h
using namespace std;
inline int read(){int ans0,w1;char cgetchar();while(!isdigit(c)c!-)cgetchar();if(c-)w-1,cgetchar();while(isdigit(c))ans(ans1)(ans3)c-0,cgetchar();return ans*w;
}
#define N 100010
int n,m,lastans0;
struct Node{int val,pos,pre,nxt;}p[N];
bool cmp(Node a,Node b){return a.preb.pre;}
//inside 原序列顺序
int ld[N*350],rd[N*350],maxv[N*350];
int cnt0;
void insert(int t,int last,int l,int r,int pos,int vl){tcnt;maxv[t]max(vl,maxv[last]);if(lr)return;ld[t]ld[last];rd[t]rd[last];int mid(lr)1;if(posmid)insert(ld[t],ld[last],l,mid,pos,vl);else insert(rd[t],rd[last],mid1,r,pos,vl);
}
int query(int t,int l,int r,int L,int R){if(!t)return 0;if(LlrR)return maxv[t];int mid(lr)1;if(Rmid)return query(ld[t],l,mid,L,R);if(Lmid)return query(rd[t],mid1,r,L,R);return max(query(ld[t],l,mid,L,R),query(rd[t],mid1,r,L,R));
}
//outside nxt顺序
int rt[N*20],lc[N*20],rc[N*20],tot0;
void insert(int t,int last,int l,int r,int key,int pos,int vl){ttot;insert(rt[t],rt[last],1,n,pos,vl);if(lr)return;lc[t]lc[last];rc[t]rc[last];int mid(lr)1;if(keymid)insert(lc[t],lc[last],l,mid,key,pos,vl);else insert(rc[t],rc[last],mid1,r,key,pos,vl);
}
int query(int t,int l,int r,int L,int R,int ql,int qr){if(!t)return 0;if(LlrR)return query(rt[t],1,n,ql,qr);int mid(lr)1;if(Rmid)return query(lc[t],l,mid,L,R,ql,qr);if(Lmid)return query(rc[t],mid1,r,L,R,ql,qr);return max(query(lc[t],l,mid,L,R,ql,qr),query(rc[t],mid1,r,L,R,ql,qr));
}
int outrt[N];
int pre[N],nxt[N];
int main(){scanf(%d%d,n,m);for(int i1;in;i)p[i].posi,scanf(%d,p[i].val);for(int i1;in;i)pre[i]0,nxt[i]n1;for(int i1;in;i)p[i].prepre[p[i].val],pre[p[i].val]i;for(int in;i1;i--)p[i].nxtnxt[p[i].val],nxt[p[i].val]i;//for(int i1;i1000;i)couti p[i].pre p[i].nxtendl;sort(p1,pn1,cmp);for(int i1;in;i)//持久化pre的顺序insert(outrt[i],outrt[i-1],1,n1,p[i].nxt,p[i].pos,p[i].val);for(int i1;im;i){int l,r;scanf(%d%d,l,r);l(llastans)%n1;r(rlastans)%n1;if(lr)swap(l,r);int ql1,qrn,tmp0;while(qlqr){int mid(qlqr)1;if(p[mid].prel)qlmid1,tmpmid;else qrmid-1;}printf(%d\n,lastansquery(outrt[tmp],1,n1,r1,n1,l,r));}return 0;
} 转载于:https://www.cnblogs.com/dream-maker-yk/p/9676288.html
