55285

CCPC2019网络赛1002 array (主席树)

题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=6703

  题意:给你一个n的全排列A,然后给m个操作,第一类操作给一个数k,将A[k^lastans]增加1000000;第二类操作在区间给两个数v,k,要求一个最小的ans,不与区间A[1,v^lastans]中任意一个数相等,并且不小于k^lastans。

  先看如果没有进行过第一种操作,对于每一次第二类操作,设r=v^lastans,k=k^lastans,因为A是一个n的全排列,如果ans不与A[1,r]中任意一个数相等,那么ans就是在A[r+1,n]中一个数,当然这个数要不小于k,所以为了防止出现在A[r+1,n]中一个数都小于k,我们在将A[n+1]赋为n+1,那么这时第二类操作的答案就是在A[r+1,n+1]中寻找一个不小于k的最小的数。这个过程可以用主席树解决。

  那么进行过第一类操作并不是意味着要更改主席树(而且改了主席树全排列就失效了),回到原Question,因为第一类操作是将一个数增加1000000,远大于n,那么显然原来的这个数就在A中不存在了,那么我们将这个数也纳入考虑范围之内,随着1操作的进行,我们就要在多个这样的数中选择最小,并且不小于k的数就行了。

  因为1操作将一个数增大,所以对于主席树的查询是没有影响的,主席树可以不用修改。

  我们只需要取两个找到的答案的最小值,就是最终的答案。

#include <iostream> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <limits.h> #include <algorithm> #include <set> #define MAXN 100010 #define mid (l+r)/2 using namespace std; int T,n,q,a[MAXN],root[MAXN]; const int inf=0x3f3f3f3f; set<int> st; struct Tree{ int tot; int L[MAXN<<5],R[MAXN<<5],sum[MAXN<<5]; void init() { tot=0; memset(L,0,sizeof(L)); memset(R,0,sizeof(R)); memset(sum,0,sizeof(sum)); } int build(int l,int r) { int id=++tot; if(l<r) { L[id]=build(l,mid); R[id]=build(mid+1,r); } return id; } int update(int pre,int l,int r,int x) { int id=++tot; L[id]=L[pre];R[id]=R[pre];sum[id]=sum[pre]+1; if(l<r) { if(x<=mid) L[id]=update(L[pre],l,mid,x); else R[id]=update(R[pre],mid+1,r,x); } return id; } int ask(int u,int v,int l,int r,int k) { if(sum[v]==sum[u]) return inf; if(l==r) return l; int ans=inf; if(k<=mid) ans=ask(L[u],L[v],l,mid,k); if(ans==inf) ans=ask(R[u],R[v],mid+1,r,k); return ans; } }tree; int main() { scanf("%d",&T); while(T--) { scanf("%d%d",&n,&q); for(int i=1;i<=n;i++) scanf("%d",&a[i]); a[n+1]=n+1; st.clear(); tree.init(); root[0]=tree.build(1,n+1); for(int i=1;i<=n+1;i++) root[i]=tree.update(root[i-1],1,n+1,a[i]); int ans=0; for(int i=1,type,u,k;i<=q;i++) { scanf("%d",&type); if(type==1) { scanf("%d",&k); k^=ans; st.insert(a[k]); } else { scanf("%d%d",&u,&k); u^=ans;k^=ans; int ans1=tree.ask(root[u],root[n+1],1,n+1,k); int ans2=inf; set<int>::iterator it=st.lower_bound(k); if(it!=st.end()) ans2=*it; ans=min(ans1,ans2); printf("%d\n",ans); } } } return 0; }

---恢复内容结束---

来源:博客园

作者:BakaCirno

链接:https://www.cnblogs.com/BakaCirno/p/11425920.html

Recommend