本文主要是介绍array（2019CCPC网络预选赛 hdu6703主席树+set）主席树求大于等于k的最小值，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
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
昨天卡了很久的一个题，你开始线段树+set一直超时，后来改了主席树，但是还是卡了很久。。
题意：要找出一个数，这个数在1~r中不能出现过，并且还要不小于k。并且读入的数据还都要异或上上一次的答案。
一开始理解错了，以为必须是数组里的数才行。但是第一个样例中就有一个数不是数组里的数，除此之外，题目中有说所有的数都是独一无二的。在执行操作1的时候，一个数加上1e7之后，就相当于作废了。因为数组中所有的数字都是不大于1e5的，所以异或之后的值也是不大于1e5的。这样的话，在加上1e7之后，就相当于这个值在1~r中删除了，又可以再用了。那这样我们把这样的值存到一个set里面，r+1到n的值用主席树去求。主席树是好多权值线段树的集合，是按着权值来的，存的是每个数的出现的个数。用主席树去求r+1 ~ n中大于等于k最小的数。
代码如下：
#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) //到达叶子节点后{if(p[rrot].sum-p[lrot].sum>0) return l;//如果这个值出现过就返回这个值，没有就返回无穷大else return inf;}int mid=l+r>>1;if(k<=mid){int ans=inf;if(k<=l)//这里相当于一个剪枝，在小于l的时候，如果左子树有符合条件的就进入左子树，否则再进入右子树。{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之间的时候，左右子树都有可能涉及，就左右都看一遍寻找最优解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的时候，直接进入右子树，左子树不用找了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);//一开始先把n+1放入集合，如果数组中的值没有符合的就输出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;
}
昨天写的超时的代码（线段树+set）当个借鉴吧
代码如下：
#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)/~
这篇关于array（2019CCPC网络预选赛 hdu6703主席树+set）主席树求大于等于k的最小值的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
