Problem Description
You are given an array a1,a2,…,an(?i∈[1,n],1≤ai≤n). Initially, each element of the array is unique.

Moreover, there are m instructions.

Each instruction is in one of the following two formats:

(1,pos),indicating to change the value of apos to apos+10,000,000;

(2,r,k),indicating to ask the minimum value which is not equal to any ai ( 1≤i≤r ) and **not less ** than k.

Please print all results of the instructions in format 2.

Input
The first line of the input contains an integer T(1≤T≤10), denoting the number of test cases.

In each test case, there are two integers n(1≤n≤100,000),m(1≤m≤100,000) in the first line, denoting the size of array a and the number of instructions.

In the second line, there are n distinct integers a1,a2,…,an (?i∈[1,n],1≤ai≤n),denoting the array.
For the following m lines, each line is of format (1,t1) or (2,t2,t3).
The parameters of each instruction are generated by such way :

For instructions in format 1 , we defined pos=t1⊕LastAns . (It is promised that 1≤pos≤n)

For instructions in format 2 , we defined r=t2⊕LastAns,k=t3⊕LastAns. (It is promised that 1≤r≤n,1≤k≤n )

(Note that ⊕ means the bitwise XOR operator. )

Before the first instruction of each test case, LastAns is equal to 0 .After each instruction in format 2, LastAns will be changed to the result of that instruction.

(∑n≤510,000,∑m≤510,000 )

Output
For each instruction in format 2, output the answer in one line.

Sample Input
3
5 9
4 3 1 2 5
2 1 1
2 2 2
2 6 7
2 1 3
2 6 3
2 0 4
1 5
2 3 7
2 4 3
10 6
1 2 4 6 3 5 9 10 7 8
2 7 2
1 2
2 0 5
2 11 10
1 3
2 3 2
10 10
9 7 5 3 4 10 6 2 1 8
1 10
2 8 9
1 12
2 15 15
1 12
2 1 3
1 9
1 12
2 2 2
1 9

Sample Output
1
5
2
2
5
6
1
6
7
3
11
10
11
4
8
11

Hint

note:
After the generation procedure ,the instructions of the first test case are :
2 1 1, in format 2 and r=1 , k=1
2 3 3, in format 2 and r=3 , k=3
2 3 2, in format 2 and r=3 , k=2
2 3 1, in format 2 and r=3 , k=1
2 4 1, in format 2 and r=4 , k=1
2 5 1, in format 2 and r=5 , k=1
1 3 , in format 1 and pos=3
2 5 1, in format 2 and r=5 , k=1
2 5 2, in format 2 and r=5 , k=2

the instructions of the second test case are :
2 7 2, in format 2 and r=7 , k=2
1 5 , in format 1 and pos=5
2 7 2, in format 2 and r=7 , k=2
2 8 9, in format 2 and r=8 , k=9
1 8 , in format 1 and pos=8
2 8 9, in format 2 and r=8 , k=9

the instructions of the third test case are :
1 10 , in format 1 and pos=10
2 8 9 , in format 2 and r=8 , k=9
1 7 , in format 1 and pos=7
2 4 4 , in format 2 and r=4 , k=4
1 8 , in format 1 and pos=8
2 5 7 , in format 2 and r=5 , k=7
1 1 , in format 1 and pos=1
1 4 , in format 1 and pos=4
2 10 10, in format 2 and r=10 , k=10
1 2 , in format 1 and pos=2
昨天卡了很久的一個(gè)題，你開(kāi)始線(xiàn)段樹(shù)+set一直超時(shí)，后來(lái)改了主席樹(shù)，但是還是卡了很久。。
題意：要找出一個(gè)數(shù)，這個(gè)數(shù)在1~r中不能出現(xiàn)過(guò)，并且還要不小于k。并且讀入的數(shù)據(jù)還都要異或上上一次的答案。
一開(kāi)始理解錯(cuò)了，以為必須是數(shù)組里的數(shù)才行。但是第一個(gè)樣例中就有一個(gè)數(shù)不是數(shù)組里的數(shù)，除此之外，題目中有說(shuō)所有的數(shù)都是獨(dú)一無(wú)二的。在執(zhí)行操作1的時(shí)候，一個(gè)數(shù)加上1e7之后，就相當(dāng)于作廢了。因?yàn)閿?shù)組中所有的數(shù)字都是不大于1e5的，所以異或之后的值也是不大于1e5的。這樣的話(huà)，在加上1e7之后，就相當(dāng)于這個(gè)值在1~r中刪除了，又可以再用了。那這樣我們把這樣的值存到一個(gè)set里面，r+1到n的值用主席樹(shù)去求。主席樹(shù)是好多權(quán)值線(xiàn)段樹(shù)的集合，是按著權(quán)值來(lái)的，存的是每個(gè)數(shù)的出現(xiàn)的個(gè)數(shù)。用主席樹(shù)去求r+1 ~ n中大于等于k最小的數(shù)。
代碼如下：

#include<bits/stdc++.h> #define ll long long #define inf 0x3f3f3f3f using namespace std;const int maxx=1e5+100; struct node{int l;int r;int sum; }p[maxx<<5]; int a[maxx]; int root[maxx]; int n,m,tot;inline void pushup(int cur) {p[cur].sum=p[p[cur].l].sum+p[p[cur].r].sum; } inline int build(int l,int r) {int cur=++tot;p[cur].sum=0;if(l==r) return cur;int mid=l+r>>1;build(l,mid);build(mid+1,r);return cur; } inline int update(int rot,int l,int r,int pos) {int cur=++tot;p[cur]=p[rot];if(l==r) {p[cur].sum++;return cur;}int mid=l+r>>1;if(pos<=mid) p[cur].l=update(p[rot].l,l,mid,pos);else p[cur].r=update(p[rot].r,mid+1,r,pos);pushup(cur);return cur; } inline int query(int lrot,int rrot,int l,int r,int k) {if(l==r) //到達(dá)葉子節(jié)點(diǎn)后{if(p[rrot].sum-p[lrot].sum>0) return l;//如果這個(gè)值出現(xiàn)過(guò)就返回這個(gè)值，沒(méi)有就返回?zé)o窮大else return inf;}int mid=l+r>>1;if(k<=mid){int ans=inf;if(k<=l)//這里相當(dāng)于一個(gè)剪枝，在小于l的時(shí)候，如果左子樹(shù)有符合條件的就進(jìn)入左子樹(shù)，否則再進(jìn)入右子樹(shù)。{if(p[p[rrot].l].sum-p[p[lrot].l].sum>0) ans=min(ans,query(p[lrot].l,p[rrot].l,l,mid,k));else if(p[p[rrot].r].sum-p[p[lrot].r].sum>0) ans=min(ans,query(p[lrot].r,p[rrot].r,mid+1,r,k));return ans;}if(p[p[rrot].l].sum-p[p[lrot].l].sum>0) //k在l到mid之間的時(shí)候，左右子樹(shù)都有可能涉及，就左右都看一遍尋找最優(yōu)解ans=min(ans,query(p[lrot].l,p[rrot].l,l,mid,k));if(p[p[rrot].r].sum-p[p[lrot].r].sum>0) ans=min(ans,query(p[lrot].r,p[rrot].r,mid+1,r,k));return ans;}else{int ans=inf;//k大于mid的時(shí)候，直接進(jìn)入右子樹(shù)，左子樹(shù)不用找了if(p[p[rrot].r].sum-p[p[lrot].r].sum>0) ans=min(ans,query(p[lrot].r,p[rrot].r,mid+1,r,k));return ans;} }int main() {int t,t1,t2,t3,op;scanf("%d",&t);ll lastans=0;while(t--){scanf("%d%d",&n,&m);set<ll> s;s.insert(n+1);//一開(kāi)始先把n+1放入集合，如果數(shù)組中的值沒(méi)有符合的就輸出n+1lastans=0;tot=0;for(int i=1;i<=n;i++) scanf("%d",&a[i]);root[0]=build(1,100001);for(int i=1;i<=n;i++) root[i]=update(root[i-1],1,100001,a[i]);while(m--){scanf("%d",&op);if(op==1){scanf("%d",&t1);t1^=lastans;s.insert(a[t1]);//把修改之后的值放入集合里}else if(op==2){scanf("%d%d",&t2,&t3);t2^=lastans,t3^=lastans;int ans=inf;if(t2!=n) ans=query(root[t2],root[n],1,100001,t3);int ans1=*s.lower_bound(t3);lastans=min(ans1,ans);printf("%d\n",lastans);}}}return 0; }

昨天寫(xiě)的超時(shí)的代碼（線(xiàn)段樹(shù)+set）當(dāng)個(gè)借鑒吧
代碼如下：

#include<bits/stdc++.h> #define ll long long #define inf 0x3f3f3f3f using namespace std;const int maxx=1e5+100; struct node{int l;int r;set<int> s; }p[maxx<<2]; int a[maxx]; int n,m;inline int read() //輸入外掛 {int res=0,ch,flag=0;if((ch=getchar())=='-')flag=1;else if(ch>='0'&&ch<='9')res=ch-'0';while((ch=getchar())>='0'&&ch<='9')res=res*10+ch-'0';return flag?-res:res; } inline void Out(int a) //輸出外掛 {if(a>9)Out(a/10);putchar(a%10+'0'); } inline void pushup(int cur) {set_union(p[cur<<1].s.begin(),p[cur<<1].s.end(),p[cur<<1|1].s.begin(),p[cur<<1|1].s.end(),inserter(p[cur].s,p[cur].s.begin())); } inline void build(int l,int r,int cur) {p[cur].l=l;p[cur].r=r;p[cur].s.clear();if(l==r) {p[cur].s.insert(a[l]);return ;}int mid=l+r>>1;build(l,mid,cur<<1);build(mid+1,r,cur<<1|1);pushup(cur); } inline set<int> query(int l,int r,int cur) {int L=p[cur].l;int R=p[cur].r;if(l<=L&&R<=r) return p[cur].s;int mid=L+R>>1;if(r<=mid) return query(l,r,cur<<1);else if(l>mid) return query(l,r,cur<<1|1);else{set<int> a=query(l,mid,cur<<1);set<int> b=query(mid+1,r,cur<<1|1);set<int> x;set_union(a.begin(),a.end(),b.begin(),b.end(),inserter(x,x.begin()));return x;} } int main() {int t,t1,t2,t3,op;t=read();while(t--){int lastans=0;n=read(),m=read();for(int i=1;i<=n;i++) a[i]=read();build(1,n,1);set<int> s;s.insert(n+1);while(m--){op=read();if(op==1){t1=read();t1^=lastans;s.insert(a[t1]);}else{t2=read(),t3=read();t2^=lastans;t3^=lastans;int ans1=inf;if(t2!=n) {set<int> s1;s1=query(t2+1,n,1);s1.insert(n+1);ans1=*s1.lower_bound(t3);}int ans2=*s.lower_bound(t3);lastans=min(ans1,ans2);Out(lastans);}}} }

努力加油a啊，(^o)/~

總結(jié)

以上是生活随笔為你收集整理的array（2019CCPC网络预选赛 hdu6703主席树+set）主席树求大于等于k的最小值的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。