题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6703
题目大意：给出一个n个元素的数组A，A中所有元素都是不重复的[1,n]。
有两种操作：
1.将pos位置的元素+1e7
2.查询不属于[1,r]中的最小的>=k的值。
强制在线。
思路：当时想的是树套树，但是O(nlong^2(n))总是超时，一直想不出有什么办法优化掉一个多余的logn，到最后都没有写出来...然后听旁边的队，用主席树+set过了，学长用裸的线段树过了。orz。听完思路后感觉好简单。哎。。还是太菜了QAQ。
Solve1：静态主席树+set。
直接用静态主席树维护区间问题。set维护删除的元素。由于查询的元素只会在[1,n+1]内出现，因此我们可以把+1e7看成删除了，因为我们最多的答案只会是n+1.对于每个删除的元素，将其插入到set中，查询的时候，查询[r+1,n+1]中第一个>=k的元素，再和set中第一个>=k的元素相比较，选择最小的就好了。
明明这么简单我怎么就没想到呢QAQ。。
ACCode：
#include<stdlib.h>
#include<string.h>
#include<stdio.h>
#include<time.h>
#include<math.h>
// srand((unsigned)time(NULL));rand();
#include<map>
#include<set>
#include<deque>
#include<queue>
#include<stack>
#include<bitset>
#include<string>
#include<fstream>
#include<iostream>
#include<algorithm>
#define ll long long
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define clean(a,b) memset(a,b,sizeof(a))
using namespace std;
const int MAXN=1e5+10;
const int INF32=0x3f3f3f3f;
const ll INF64=0x3f3f3f3f3f3f3f3f;
const ll MOD=1e9+7;
const double PI=acos(-1.0);
const double EPS=1.0e-8;
//unsigned register
// ios::sync_with_stdio(false)
// freopen(".in","r",stdin);freopen(".out","w",stdout);
struct ChairTree{
int Rt[MAXN<<5],Lc[MAXN<<5],Rc[MAXN<<5],Siz[MAXN<<5];
int NodeCnt;
void Build(int l,int r,int &rt){
rt=++NodeCnt;
if(l==r) return ;
int mid=(l+r)>>1;
Build(l,mid,Lc[rt]);Build(mid+1,r,Rc[rt]);
}
int Modify(int pos,int l,int r,int rt){
int Nrt=++NodeCnt;
Lc[Nrt]=Lc[rt];Rc[Nrt]=Rc[rt];Siz[Nrt]=Siz[rt]+1;
if(l==r) return Nrt;
int mid=(l+r)>>1;
if(pos<=mid) Lc[Nrt]=Modify(pos,l,mid,Lc[Nrt]);
if(pos>mid) Rc[Nrt]=Modify(pos,mid+1,r,Rc[Nrt]);
return Nrt;
}
int Query(int ql,int qr,int l,int r,int k){
//[ql,qr]中找第一个>=k
// printf("ql=%d qr=%d l=%d r=%d k=%d\n",ql,qr,l,r,k);
if(l==r) return l;
int x1=Siz[Lc[qr]]-Siz[Lc[ql]],x2=Siz[Rc[qr]]-Siz[Rc[ql]];
// printf("x1=%d x2=%d\n",x1,x2);
//该区间中没有可用的元素
//if(Siz[Rt[qr]]-Siz[Rt[ql]]==0) return INF32;
int mid=(l+r)>>1;
int Ans=INF32;
//[l,mid]中可能存在一个数>=k
if(mid>=k&&x1) Ans=Query(Lc[ql],Lc[qr],l,mid,k);
// printf("go l Ans=%d\n",Ans);
if(Ans!=INF32) return Ans;
//[mid+1,r]中必定存在一个数>=k
if(x2) Ans=Query(Rc[ql],Rc[qr],mid+1,r,k);
return Ans;
}
void Intt(int l,int r){
NodeCnt=0;
Build(l,r,Rt[0]);
}
void Update(int pos,int l,int r,int i){
Rt[i]=Modify(pos,l,r,Rt[i-1]);
}
int Ans(int ql,int qr,int l,int r,int k){
return Query(Rt[ql-1],Rt[qr],l,r,k);
}
};
ChairTree CT;
set<int> Set;
int A[MAXN];
int B[MAXN];
int n,m;
int main(){
freopen("1002.in","r",stdin);//freopen("1002.out","w",stdout);
int T;scanf("%d",&T);
while(T--){
Set.clear();
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) scanf("%d",&A[i]);
CT.Intt(1,n+1);
for(int i=1;i<=n;++i) CT.Update(A[i],1,n+1,i);
CT.Update(n+1,1,n+1,n+1);
int Ans=0;
while(m--){
int opt;scanf("%d",&opt);
if(opt==1){
int t1,pos;scanf("%d",&t1);
pos=t1^Ans;
Set.insert(A[pos]);
}
else{
int t2,t3,r,k;scanf("%d%d",&t2,&t3);
r=t2^Ans;k=t3^Ans;
// printf("Query:ql=%d qr=%d k=%d\n",r+1,n+1,k);
Ans=CT.Ans(r+1,n+1,1,n+1,k);//[r+1,n+1]中第一个>=k的数
if(Set.size()){
set<int>::iterator it=Set.lower_bound(k);
if(it!=Set.end()) Ans=min(*it,Ans);
}printf("%d\n",Ans);
}
}
}
}
Solve2：权值线段树
将数组元素进行排序，然后根据其下标建立权值线段树，维护下标的最大值。
修改的时候，将对应的值在线段树中的下标修改为INF32就好了。
查询的时候，查询[k,n+1]区间内找到第一个下标>r的位置。注意是下标，因为不能在[1,r]中出现，所以是第一个>r的元素。
ACCode：
#include<stdlib.h>
#include<string.h>
#include<stdio.h>
#include<time.h>
#include<math.h>
// srand((unsigned)time(NULL));rand();
#include<map>
#include<set>
#include<deque>
#include<queue>
#include<stack>
#include<bitset>
#include<string>
#include<fstream>
#include<iostream>
#include<algorithm>
#define ll long long
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define clean(a,b) memset(a,b,sizeof(a))
using namespace std;
const int MAXN=1e5+10;
const int INF32=0x3f3f3f3f;
const ll INF64=0x3f3f3f3f3f3f3f3f;
const ll MOD=1e9+7;
const double PI=acos(-1.0);
const double EPS=1.0e-8;
//unsigned register
// ios::sync_with_stdio(false)
// freopen(".in","r",stdin);freopen(".out","w",stdout);
struct SegTree{
struct Node{
int l,r,len;
int id,mx;
};
Node Tree[MAXN<<2];
void PushUp(int rt){
Tree[rt].mx=max(Tree[rt<<1].mx,Tree[rt<<1|1].mx);
}
void Build(int l,int r,int rt,int A[]){
Tree[rt].l=l;Tree[rt].r=r;Tree[rt].len=r-l+1;
if(l==r){
Tree[rt].id=Tree[rt].mx=A[l];
return ;
}int mid=(l+r)>>1;
Build(l,mid,rt<<1,A);Build(mid+1,r,rt<<1|1,A);
PushUp(rt);
}
void Update(int pos,int val,int rt){
if(Tree[rt].l==Tree[rt].r){
Tree[rt].id=Tree[rt].mx=val;
return ;
}
if(pos<=Tree[rt<<1].r) Update(pos,val,rt<<1);
else Update(pos,val,rt<<1|1);
PushUp(rt);
}
int Query(int ql,int qr,int val,int rt){
//在[ql,qr]内找到第一个>val的
// printf("ql=%d qr=%d val=%d l=%d r=%d mx=%d\n",ql,qr,val,Tree[rt].l,Tree[rt].r,Tree[rt].mx);
if(Tree[rt].l==Tree[rt].r) return Tree[rt].l;
int Ans=INF32;
// printf("(rt<<1): l=%d r=%d mx=%d\n",Tree[rt<<1].l,Tree[rt<<1].r,Tree[rt<<1].mx);
if(ql<=Tree[rt<<1].r&&val<Tree[rt<<1].mx) Ans=Query(ql,qr,val,rt<<1);
// printf("go l Ans=%d\n",Ans);
if(Ans!=INF32) return Ans;
// printf("(rt<<1|1): l=%d r=%d mx=%d\n",Tree[rt<<1|1].l,Tree[rt<<1|1].r,Tree[rt<<1|1].mx);
if(qr>=Tree[rt<<1|1].l&&val<Tree[rt<<1|1].mx) Ans=Query(ql,qr,val,rt<<1|1);
// printf("go r Ans=%d\n",Ans);
return Ans;
}
void Show(int rt){
printf("l=%d r=%d mx=%d\n",Tree[rt].l,Tree[rt].r,Tree[rt].mx);
if(Tree[rt].l==Tree[rt].r) return ;
Show(rt<<1);Show(rt<<1|1);
}
};
SegTree Seg;
PII A[MAXN];
int B[MAXN];
int n,m;
int Cmp1(PII a,PII b){
return a.second<b.second;
}
int main(){
//freopen("1002.in","r",stdin);//freopen("1002.out","w",stdout);
int T;scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
scanf("%d",&A[i].first);
A[i].second=i;
}sort(A+1,A+1+n);
for(int i=1;i<=n;++i){
B[i]=A[i].second;
}sort(A+1,A+1+n,Cmp1);
// for(int i=1;i<=n;++i) printf("%d ",B[i]);printf("\n");
B[++n]=INF32;
Seg.Build(1,n,1,B);
int Ans=0;
while(m--){
int opt;scanf("%d",&opt);
if(opt==1){
int t1,pos;scanf("%d",&t1);
pos=t1^Ans;
Seg.Update(A[pos].first,INF32,1);
// printf("Update:%d\n",pos);Seg.Show(1);printf("\n");
}
else{
int t2,t3,r,k;scanf("%d%d",&t2,&t3);
r=t2^Ans;k=t3^Ans;//在[k,n]区间内找第一个>r的位置
printf("%d\n",Ans=Seg.Query(k,n,r,1));
}
}
}
}
![template，泛型实现阉割版的优先队列（一次简单的尝试）[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)