- 题意
- 给一个1~n的序列(非有序,n<=100000),m个操作
- 1,t1:pos = lastans ^ t1, 令a[pos] += 1000000
- 2,t2,t3:r = lastans^t2, k = lastans^t3, 查询在大于等于k且未在a[1]~a[r]中出现的最小值
- 给一个1~n的序列(非有序,n<=100000),m个操作
- 题解
- 看数据范围,我们可以考虑建立一颗[1, n+1](因为有可能输出n+1)的权值线段树
- 每个结点中存储下标的最大值
- 当我们执行操作2时,直接查询[k,n]中第一个大于r的下标,输出储存该下标的位置即可
- 当我们执行操作1时,发现只要执行了操作1,就会使得该数空出来,那么直接将其储存的下标最大值赋一个大于n+1的数即可
- 看数据范围,我们可以考虑建立一颗[1, n+1](因为有可能输出n+1)的权值线段树
- 代码
-
#include<algorithm> #include <iostream> #include <fstream> #include <cstdlib> #include <cstring> #include <cassert> #include <cstdio> #include <vector> #include <string> #include <cmath> #include <queue> #include <stack> #include <set> #include <map> using namespace std; #define P(a,b,c) make_pair(a,make_pair(b,c)) #define rep(i,a,n) for (int i=a;i<=n;i++) #define per(i,a,n) for (int i=n;i>=a;i--) #define CLR(vis) memset(vis,0,sizeof(vis)) #define MST(vis,pos) memset(vis,pos,sizeof(vis)) #define pb push_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define se second #define SZ(x) ((int)(x).size()) typedef pair<int,pair<int,int> >pii; typedef long long ll; typedef unsigned long long ull; const ll mod = 1000000007; const int INF = 0x3f3f3f3f; ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; } template<class T>inline void gmax(T &A, T B) { (A<B)&&(A=B);//if(B>A)A=B; } template<class T>inline void gmin(T &A, T B) { (A>B)&&(A=B);//if(B<A)A=B; } template <class T> inline bool scan(T &ret) { char c; int sgn; if(c=getchar(),c==EOF) return 0; //EOF while(c!='-'&&(c<'0'||c>'9')) c=getchar(); sgn=(c=='-')?-1:1; ret=(c=='-')?0:(c-'0'); while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0'); ret*=sgn; return 1; } inline void outt(int x) { if(x>9) outt(x/10); putchar(x%10+'0'); } const int maxn=1e6+10; struct SegmentTree { int l,r,dat; #define l(x) tree[x].l #define r(x) tree[x].r #define m(x) tree[x].dat } tree[maxn * 4]; void build(int p,int l,int r,int *a) { l(p)=l,r(p)=r; if(l==r){ m(p)=a[l]; return ; } int mid = (l+r)>>1; build(p<<1,l,mid,a); build(p<<1|1,mid+1,r,a); m(p)=max(m(p<<1),m(p<<1|1)); // cout<<m(p)<<endl; } void update(int p,int val,int pos) { if(l(p)==r(p)){ m(p) = val; return ; } if(pos < l(p<<1|1))update(p<<1,val,pos); else update(p<<1|1,val,pos); m(p) = max(m(p<<1),m(p<<1|1)); } int query(int p,int l,int r,int val){ if(l(p)==r(p))return l(p); int ans = INF; if(r(p<<1) >= l && m(p<<1) > val)ans = query(p<<1,l,r,val); if(ans!=INF)return ans; if(l(p<<1|1) <= r && m(p<<1|1) > val) ans = query(p<<1|1,l,r,val); return ans; } int a[maxn],b[maxn]; int main() { int t; scanf("%d", &t); while(t--) { int n,q; scanf("%d%d", &n, &q); rep(i,1,n) { scanf("%d", &a[i]); b[a[i]] = i; } b[++n]=INF; build(1,1,n,b); int ans=0; int op,t1,t2,t3; int r,k,pos; while(q--){ scanf("%d", &op); if(op==1){ scanf("%d", &t1); pos = t1^ans; //空出pos,即将pos的位置置为INF,这样刚好满足询问时找到第一个存储的下标大于r的要求 update(1,INF,a[pos]); }else{ scanf("%d%d", &t2,&t3); r = ans^t2; k = ans^t3; printf("%d\n", ans = query(1,k,n,r)); } } } return 0; }
-
本题还可以用主席树做,稍后补上