2019ccpc网络赛hdu6703 array(线段树)

array

题目传送门

解题思路

操作1是把第pos个位置上的数加上\(10^7\)，操作2是找到区间[1,r]中没有且大于k的最小的数。注意到k的范围是小于等于n的，且n的范围是\(10^5\)，远小于\(10^7\)，所以对于操作1，可以视为把第pos个位置上的数删去。

因为所有节点上的数都是唯一的，所以建立一颗权值线段树，存入每个权值对应的位置，维护其最大值和最小值。为了保证一定有答案，建立的权值范围是[1,n+1]。对于操作1，直接把pos对应的权值的叶子节点修改为0，代表这个数不存在即可。

对于操作2，我们在线段树上查询。对于一颗子树，有答案的前提是其最大值大于r，或者最小值等于0，即存在r后面的数，或者有不存在的数。对于左子树，还应有mid>=k。因为答案要尽量小，所以先看左子树是否可以找到答案，如果左子树没有答案，再看右子树，如果右子树也没有，则返回0，表示没有找到答案。但因为建立的权值范围是[1,n+1]，所以最后一定会有答案，当进入叶子节点，则返回答案。

代码如下

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f

using namespace std;

typedef long long ll;

const int N = 100005;

struct T{

    int l, r;

    int minn, maxx;

}tree[N<<2];

void build(int k, int l, int r)

{

    tree[k].l = l;

    tree[k].r = r;

    tree[k].maxx = tree[k].minn = 0;

    if(l == r)

        return;

    int mid = (l + r) / 2;

    build(2*k, l, mid);

    build(2*k+1, mid + 1, r);

}

void update(int k, int x, int v)

{

    if(tree[k].l == tree[k].r){

        tree[k].maxx = tree[k].minn = v;

        return;

    }

    int mid = (tree[k].l + tree[k].r) / 2;

    if(x <= mid)

        update(2*k, x, v);

    else

        update(2*k+1, x, v);

    tree[k].minn = min(tree[2*k].minn, tree[2*k+1].minn);

    tree[k].maxx = max(tree[2*k].maxx, tree[2*k+1].maxx);

}

int query(int k, int r, int x)

{

    if(tree[k].l == tree[k].r)

        return tree[k].l;

    int mid = (tree[k].l + tree[k].r) / 2;

    if(x <= mid && (tree[2*k].minn == 0 || tree[2*k].maxx > r)){

        int ans = query(2*k, r, x);

        if(ans)

            return ans;

    }

    if(tree[2*k+1].minn == 0 || tree[2*k+1].maxx > r)

        return query(2*k+1, r, x);

    else

        return 0;

}

int a[N];

int main()

{

    int t;

    scanf("%d", &t);

    while(t --){

        int n, m;

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

        build(1, 1, n + 1);

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

            int x;

            scanf("%d", &x);

            a[i] = x;

            update(1, x, i);

        }

        int last = 0;

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

            int opt;

            scanf("%d", &opt);

            if(opt == 1){

                int t1;

                scanf("%d", &t1);

                t1 ^= last;

                update(1, a[t1], 0);

            }

            else {

                int t1, t2;

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

                t1 ^= last;

                t2 ^= last;

                last = query(1, t1, t2);

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

            }

        }

    }

    return 0;

}