HDU-6703 array(权值线段树)

• 题意
  • 给一个1~n的序列（非有序,n<=100000），m个操作
    • 1，t1：pos = lastans ^ t1，  令a[pos] += 1000000
    • 2，t2，t3：r = lastans^t2, k = lastans^t3,   查询在大于等于k且未在a[1]~a[r]中出现的最小值
• 题解
  • 看数据范围，我们可以考虑建立一颗[1, n+1]（因为有可能输出n+1）的权值线段树
    • 每个结点中存储下标的最大值
    • 当我们执行操作2时，直接查询[k,n]中第一个大于r的下标，输出储存该下标的位置即可
    • 当我们执行操作1时，发现只要执行了操作1，就会使得该数空出来，那么直接将其储存的下标最大值赋一个大于n+1的数即可
• 代码

  • #include<algorithm>
    #include <iostream>
    #include   <fstream>
    #include  <cstdlib>
    #include  <cstring>
    #include  <cassert>
    #include   <cstdio>
    #include   <vector>
    #include   <string>
    #include    <cmath>
    #include    <queue>
    #include    <stack>
    #include      <set>
    #include      <map>
    using namespace std;
    #define P(a,b,c) make_pair(a,make_pair(b,c))
    #define rep(i,a,n) for (int i=a;i<=n;i++)
    #define per(i,a,n) for (int i=n;i>=a;i--)
    #define CLR(vis) memset(vis,0,sizeof(vis))
    #define MST(vis,pos) memset(vis,pos,sizeof(vis))
    #define pb push_back
    #define mp make_pair
    #define all(x) (x).begin(),(x).end()
    #define fi first
    #define se second
    #define SZ(x) ((int)(x).size())
    typedef pair<int,pair<int,int> >pii;
    typedef long long ll;
    typedef unsigned long long ull;
    const ll mod = 1000000007;
    const int INF = 0x3f3f3f3f;
    ll gcd(ll a, ll b) {
        return b ? gcd(b, a%b) : a;
    }
    template<class T>inline void gmax(T &A, T B) {
        (A<B)&&(A=B);//if(B>A)A=B;
    }
    template<class T>inline void gmin(T &A, T B) {
        (A>B)&&(A=B);//if(B<A)A=B;
    }
    template <class T>
    inline bool scan(T &ret) {
        char c;
        int sgn;
        if(c=getchar(),c==EOF) return 0; //EOF
        while(c!='-'&&(c<'0'||c>'9')) c=getchar();
        sgn=(c=='-')?-1:1;
        ret=(c=='-')?0:(c-'0');
        while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
        ret*=sgn;
        return 1;
    }
    inline void outt(int x) {
        if(x>9) outt(x/10);
        putchar(x%10+'0');
    }
    const int maxn=1e6+10;
    
    
    struct SegmentTree {
        int l,r,dat;
        #define l(x) tree[x].l
        #define r(x) tree[x].r
        #define m(x) tree[x].dat
    } tree[maxn * 4];
    
    void build(int p,int l,int r,int *a) {
        l(p)=l,r(p)=r;
        if(l==r){
            m(p)=a[l];
            return ;
        }
        int mid = (l+r)>>1;
        build(p<<1,l,mid,a);
        build(p<<1|1,mid+1,r,a);
        m(p)=max(m(p<<1),m(p<<1|1));
    //    cout<<m(p)<<endl;
    }
    
    void update(int p,int val,int pos) {
        if(l(p)==r(p)){
            m(p) = val;
            return ;
        }
        if(pos < l(p<<1|1))update(p<<1,val,pos);
        else update(p<<1|1,val,pos);
        m(p) = max(m(p<<1),m(p<<1|1));
    }
    
    int query(int p,int l,int r,int val){
        if(l(p)==r(p))return l(p);
        int ans = INF;
        if(r(p<<1) >= l && m(p<<1) > val)ans = query(p<<1,l,r,val);
        if(ans!=INF)return ans;
        if(l(p<<1|1) <= r && m(p<<1|1) > val) ans = query(p<<1|1,l,r,val);
        return ans;
    }
    int a[maxn],b[maxn];
    
    int main() {
        int t;
        scanf("%d", &t);
        while(t--) {
            int n,q;
            scanf("%d%d", &n, &q);
            rep(i,1,n) {
                scanf("%d", &a[i]);
                b[a[i]] = i;
            }
            b[++n]=INF;
            build(1,1,n,b);
            int ans=0;
            int op,t1,t2,t3;
            int r,k,pos;
            while(q--){
                scanf("%d", &op);
                if(op==1){
                    scanf("%d", &t1);
                    pos = t1^ans;
                    //空出pos，即将pos的位置置为INF，这样刚好满足询问时找到第一个存储的下标大于r的要求 
                    update(1,INF,a[pos]); 
                }else{
                    scanf("%d%d", &t2,&t3);
                    r = ans^t2;
                    k = ans^t3;
                    printf("%d\n", ans = query(1,k,n,r));
                }
            }
        }
        return 0;
    }

本题还可以用主席树做，稍后补上