本文共 2127 字，大约阅读时间需要 7 分钟。
主席树维护最小值 如果一个数被插入队列，相当于这个数无法被选 inf 如果一个数加1e7；相当于这个数又可以被选 实际维护+1e7的操作比较麻烦 直接用将+1e7的数字压入set中二分找>=k的最小的数在于查找的答案去min
主席树维护最小值
如果一个数被插入队列，相当于这个数无法被选 inf
如果一个数加1e7；相当于这个数又可以被选
实际维护+1e7的操作比较麻烦
直接用将+1e7的数字压入set中二分找>=k的最小的数在于查找的答案去min
#include #include #include #include #include #include #include #include #include #include #include #define inf 0x3f3f3f3f#define mem(a,b) memset(a,b,sizeof(a))#define ll long long#define sd(x) scanf("%d",&(x))#define sl(x) scanf("%lld",&(x))#define slf(x) scanf("%lf",&(x))#define scs(s) scanf("%s",s)#define rep(i,a,b) for(int i=a;i<=b;i++)#define per(i,a,b) for(int i=a;i>=b;i--)#define lowbit(x) x&(-x)#define ls now<<1#define rs now<<1|1#define lson l,mid,ls#define rson mid+1,r,rs#define All L,Rusing namespace std;const int maxn=5e5+10;struct Node{ int l,r,s;}tree[maxn*32];int a[maxn];int root[maxn],Min[maxn*32];int n,m,tot=0,k=0;int built(int l,int r){ int mid=(l+r)>>1; int now=++k; if(l==r) { Min[now]=l; return now; } tree[now].l=built(l,mid); tree[now].r=built(mid+1,r); Min[now]=min(Min[tree[now].l],Min[tree[now].r]); return now;}int update(int pre,int p,int l,int r){ int mid=(l+r)>>1; int now=++k; tree[now].l=tree[pre].l; tree[now].r=tree[pre].r; if(l==r) { Min[now]=1e9; return now; } if(p<=mid) tree[now].l=update(tree[pre].l,p,l,mid); else tree[now].r=update(tree[pre].r,p,mid+1,r); Min[now]=min(Min[tree[now].l],Min[tree[now].r]); return now;}int query(int now,int l,int r,int L,int R){ int mid=(l+r)/2; if(l>=L&&r<=R){ return Min[now]; } int ans=1e9; if(L<=mid)ans=min(ans,query(tree[now].l,l,mid,L,R)); if(R>mid)ans=min(ans,query(tree[now].r,mid+1,r,L,R)); return ans;}int main(){ int t; int h=1e5+1; cin>>t; root[0]=built(1,h); while(t--) { int last=0; cin>>n>>m; for(int i=1;i<=n;i++) { cin>>a[i]; root[i]=update(root[i-1],a[i],1,h); } set s; while(m--) { int cmd,t1,t2,t3; sd(cmd); if(cmd==1) { sd(t1); t1^=last; s.insert(a[t1]); } else { sd(t2),sd(t3); t2^=last; t3^=last; int a1=query(root[t2],1,h,t3,h); int a2=1e9; auto it=s.lower_bound(t3); if(it!=s.end()) a2=*it; last=min(a1,a2); cout< <<"\n"; } } } return 0;}
转载于:https://www.cnblogs.com/minun/p/11428431.html