HDU 6703 array

题意：

给定一个数组 \(a_1,a_2, a_3,...a_n\) ，满足 \(1 \le a[i]\le n\) 且 \(a[i]\) 互不相同。

有两种操作：1. 将 \(a_{pos}\) 的值加上 100000000；2. 询问不等于任何 \(a[i], (1 \le i \le r)\) 且不小于 \(k\) 的最小值。

思路：

注意 \(n,k\) 的范围都不超过 100000，对于操作一，相当于删除了这个数（询问的答案一定在区间 \([k, n+1]\) 内）。

现在问题转化为：

求值在 \([k,n+1]\) 内并且坐标大于 \(r\) 的最小值。

我们用线段树节点表示 \(a_i\) 的值，每个节点维护当前区间 \([l, r]\) 的下标最大值。那么query每次先找左子树（下标更小），没找到再找右子树。

AC代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define lson rt<<1, l, mid

#define rson rt<<1|1, mid+1, r

const int maxn = 100010;

const int INF = 0x3f3f3f3f;

int tree[maxn<<2];

int arr[maxn];

int id[maxn];

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

    if(l==r) {

        tree[rt] = id[l];

        return;

    }

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

    build(lson);

    build(rson);

    tree[rt] = max(tree[rt<<1], tree[rt<<1|1]);

}

int query(int L, int R, int rt, int l, int r, int val) {

    if(l==r) {

        return l;

    }

    int ans = INF;

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

    if(L<=mid && val<tree[rt<<1])

        ans = query(L, R, lson, val);

    if(ans!=INF) return ans;

    if(mid<R && val<tree[rt<<1|1])

        ans = query(L, R, rson, val);

    return ans;

}

void update(int rt, int l, int r, int pos) {

    if(l==r) {

        tree[rt] = INF;

        return;

    }

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

    if(pos<=mid)

        update(lson, pos);

    else

        update(rson, pos);

    tree[rt] = max(tree[rt<<1], tree[rt<<1|1]);

}

int n, m;

int main() {

    int t; cin>>t;

    while(t--) {

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

        int len = 0;

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

            scanf("%d", &arr[i]);

            id[arr[i]] = i;

            len = max(len, arr[i]);

        }

        id[++len] = INF;

        build(1, 1, len);

        int ans = 0;

        while(m--) {

            int op;

            scanf("%d", &op);

            if(op==1) {

                int pos;

                scanf("%d", &pos);

                pos = pos^ans;

                update(1, 1, len, arr[pos]);

            } else {

                int r, k;

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

                r = r^ans, k = k^ans;

                ans = query(k, len, 1, 1, len, r);

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

            }

        }

        memset(id, 0, sizeof(id));

    }    

    return 0;

}

巴特西

CCPC 2019 网络赛 1002 array （权值线段树）

HDU 6703 array

题意：

思路：

AC代码：

最新文章

热门文章