hdu 6703 array(权值线段树)

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. (1,pos),indicating to change the value of apos to apos+10,000,000;
2. (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.

思路

有两种nlogn的解法、

其一：用权值线段树维护出现的下标然后维护一下区间最大值对于1操作我们可以直接把下标变大对于操作二我们可以区间查询到底但是要加上一个判断就是当前子树的

最大下标是否大于输入的位置。

其二：我们可以同样考虑用权值线段树维护当前的最左位置这样建立可持久化线段树以后我们就可以解决不修改的查询操作对于操作一我们可以考虑用一个set维护那么对于某一查询要么就是

直接查出来的值要么就是set里面的值我们选一个最小的即可。

解法一：

#include <bits/stdc++.h>

using namespace std;

const double pi = acos(-1.0);

const int N = 1e5+7;

const int inf = 0x3f3f3f3f;

const double eps = 1e-6;

typedef long long ll;

const ll mod = 1e9+7;

int a[N],po[N];

struct tree{

    int l,r,v;

}t[N<<2];

void build(int p,int l,int r){

    t[p].l=l; t[p].r=r;

    if(l==r){

        t[p].v=po[l];

        //cout<<t[p].l<<" "<<t[p].r<<" "<<t[p].v<<endl;

        return ;

    }

    int mid=(l+r)>>1;

    build(p<<1,l,mid);

    build(p<<1|1,mid+1,r);

    t[p].v=max(t[p<<1].v,t[p<<1|1].v);

}

void update(int p,int x,int v){

    if(t[p].l==t[p].r&&t[p].l==x){

        t[p].v=v;

        po[t[p].l]=v;

        return ;

    }

    int mid=(t[p].l+t[p].r)>>1;

    if(x<=mid) update(p<<1,x,v);

    else update(p<<1|1,x,v);

    t[p].v=max(t[p<<1].v,t[p<<1|1].v);

}

int query(int p,int l,int r,int pos){

//    cout<<t[p].l<<" "<<t[p].r<<endl;

    if(t[p].l==t[p].r){

        return t[p].l;

    }

    int mid=(t[p].l+t[p].r)>>1;

    int res;

    if(t[p<<1].v>pos){

        if(l<=mid) res=query(p<<1,l,r,pos);

        if(po[res]>pos) return res;

        if(r>mid) res=query(p<<1|1,l,r,pos);

    }else{

        if(r>mid) res=query(p<<1|1,l,r,pos);

    }

    return res;

}

int main(){

//    ios::sync_with_stdio(false);

//    cin.tie(0); cout.tie(0);

    int t; scanf("%d",&t);

    while(t--){

        memset(po,0,sizeof(po));

        int n,m; scanf("%d%d",&n,&m);

        for(int i=1;i<=n;i++) scanf("%d",a+i),po[a[i]]=i;

        po[n+1]=n+1;

        a[n+1]=n+1;

        build(1,1,n+1);

        int lastans=0,ans;

        for(int i=1;i<=m;i++){

            int op,r,k;

            scanf("%d%d",&op,&r);

            if(op==1){

                r=r^lastans;

                //printf("%d\n",a[r]);

                update(1,a[r],n+1);

            }else{

                scanf("%d",&k);

                r=r^lastans; k=k^lastans;

                //cout<<r<<" "<<k<<" "<<lastans<<endl;

                ans=query(1,k,n+1,r);

                lastans=ans;

                printf("%d\n",ans);

            //    cout<<ans<<"\n";

            }

        }

    }

}

解法二：

#include <bits/stdc++.h>

using namespace std;

const double pi = acos(-1.0);

const int N = 1e5+7;

const int inf = 0x3f3f3f3f;

const double eps = 1e-6;

typedef long long ll;

const ll mod = 1e7+9;

int a[N],rt[N];

struct tree{

    int l,r,v;

    int ls,rs;

}t[N<<5];

set<int> s;

int nico=0;

int cnt=0;

void build(int &p,int l,int r){

    p=++nico;

    t[p].l=l; t[p].r=r;

    if(l==r){

        t[p].v=l;

        return ;

    }

    int mid=(l+r)>>1;

    build(t[p].ls,l,mid);

    build(t[p].rs,mid+1,r);

    t[p].v=min(t[t[p].ls].v,t[t[p].rs].v);

}

void update(int &p,int last,int x,int v){

    p=++cnt;

    t[p]=t[last];

    if(t[p].l==t[p].r&&t[p].l==x){

        t[p].v=v;

        return ;

    }

    int mid=(t[p].l+t[p].r)>>1;

    if(x<=mid) update(t[p].ls,t[last].ls,x,v);

    else update(t[p].rs,t[last].rs,x,v);

    t[p].v=min(t[t[p].ls].v,t[t[p].rs].v);

}

int query(int p,int l,int r){

    if(l<=t[p].l&&t[p].r<=r){

        return t[p].v;

    }

    int mid=(t[p].l+t[p].r)>>1;

    int ans=inf;

    if(l<=mid) ans=min(ans,query(t[p].ls,l,r));

    if(mid<r) ans=min(ans,query(t[p].rs,l,r));

    return ans;

}

int main(){

//    ios::sync_with_stdio(false);

//    cin.tie(0); cout.tie(0);

    int t; scanf("%d",&t);

    while(t--){

        s.clear();

        int n,m; scanf("%d%d",&n,&m);

        build(rt[0],1,n+1);

        cnt=nico;

        for(int i=1;i<=n;i++){

            scanf("%d",a+i);

            update(rt[i],rt[i-1],a[i],inf);

        }

        int lastans=0; int nowans;

        for(int i=1;i<=m;i++){

            int op,t1,t2;

            scanf("%d",&op);

            if(op==1){

                scanf("%d",&t1);

                t1=t1^lastans;

                s.insert(a[t1]);

            }else{

                scanf("%d%d",&t1,&t2);

                t1=t1^lastans; t2=t2^lastans;

                auto v=s.lower_bound(t2);

                if(v!=s.end()){

                    nowans=min(*v,query(rt[t1],t2,n+1));

                }else{

                    nowans=query(rt[t1],t2,n+1);

                }

                lastans=nowans;

                printf("%d\n",nowans);

            }

        }

    }

}

巴特西

hdu 6703 array(权值线段树)

Problem Description

Input

Output

思路

最新文章

热门文章