CCPCネットワーク試合HDU-6703 array(主席樹+set+思考)(クエリー区間内の最初のk以上の数テンプレート)

リンク:http://acm.hdu.edu.cn/showproblem.php?pid=6703
标题:複数のサンプル.1~nの全配列を与え、m個の操作、操作は2種類あり、第1の操作はa[pos]+1 e 7である.第2の質問は[1,r]区間内のkより小さくない数ではない.オンライン照会を強制します.
構想:nは1 e 5未満であり、各数に加算されるのは1 e 7であるため、第1の操作の数は、この数を削除することに相当する.2番目の操作毎の答えの範囲は[1,n+1]である.この答えは,以前の第1の操作で削除された数のうち,[r+1,n]という区間内の数のうち,探し出すたびにn+1と最小値を取ればよい.
PS:%坤神,tqltqltql.また、彼のテンプレートは本当に使いやすいです.

#include
#include
#include
#include
#include
#include 
using namespace std;
#define M(a, b) memset(a, b, sizeof(a))
#define lowbit(x) (x&(-x))
typedef long long ll;
const int N=1e5+10;
 
struct node
{
    int l,r;
    int val;
}tree[N*22];
int n,q,a[N],root[N],cnt,temp;
set s;
set::iterator it;
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 write(int a)    
{
    if(a>9)
        write(a/10);
    putchar(a%10+'0');
}
inline int update(int up,int tar,int l,int r)
{
    int cur=cnt++;//     ，     
    tree[cur]=tree[up];//            
    tree[cur].val++;
    if(l==r) return cur;
    int mid=(r+l)>>1;
    //           
    if(tar<=mid) tree[cur].l=update(tree[up].l,tar,l,mid);
    else tree[cur].r=update(tree[up].r,tar,mid+1,r);
    return cur;
}
//  [pl,pr]   tar      
inline int query(int pl,int pr,int l,int r,int tar)
{
    if(l==r) return l;
    int mid=(r+l)>>1,lnum,rnum,res=N;
	lnum=tree[tree[pr].l].val-tree[tree[pl].l].val;
	rnum=tree[tree[pr].r].val-tree[tree[pl].r].val;
	//  tar    [l,r]  
	if(tar>=l)
	{
		//       [l,mid]   ，            0 
		if(tar<=mid&&lnum>0)
		{
			temp=query(tree[pl].l,tree[pr].l,l,mid,tar);
			if(temp0)
		{
			temp=query(tree[pl].r,tree[pr].r,mid+1,r,tar);
			res=min(res,temp);	
		} 		
	}
	//tar     l 
	else
	{
		//            0 
		if(lnum>0)
		{
			temp=query(tree[pl].l,tree[pr].l,l,mid,tar);
			if(temp0)
		{
			temp=query(tree[pl].r,tree[pr].r,mid+1,r,tar);
			res=min(res,temp);
		} 
	}
	return res;
}
int main()
{
	int t,ans,op,pos,r,k,ans1,ans2;
	t=read();//scanf("%d",&t);
    while(t--)
    {
    	n=read(),q=read();//scanf("%d%d",&n,&q); 
    	s.clear();
    	cnt=0; 
    	ans=0;
        for(int i=1;i<=n;i++)
        {
        	a[i]=read();//scanf("%d",&a[i]);
        	root[i]=update(root[i-1],a[i],1,n);
		}            
        while(q--)
        {
            op=read();//scanf("%d",&op);
			if(op==1)
			{
				pos=read();//scanf("%d",&pos);
				pos^=ans;
				s.insert(a[pos]);
			}
			else
			{
				r=read(),k=read();//scanf("%d%d",&r,&k);
				r^=ans,k^=ans;
				ans1=n+1,ans2=n+1;
				
				it=s.lower_bound(k);
				if(it!=s.end()) ans1=*it;
				
				if(r!=n)
				{
					temp=query(root[r],root[n],1,n,k);
					if(ans2>temp)
						ans2=temp;
				}	
				write(ans=min(ans1,ans2));
				putchar('
');	
				//printf("%d
",ans=min(ans1,ans2));
			}
	    }
    }
 
	return 0;
}