HDU6703-array(权值线段树/主席树+set,树上二分)

题目链接:HDU6703-array

题意:

给定一个长度为n的序列,序列中的元素为1-n,不会重复出现,然后有两个操作:

  1. 把某个数加上10000000;
  2. 查询一个数,要求这个数不小于k,且在序列前r个中没出现过,求出这个数的最小值。

题解:

做法一:权值线段树+二分

线段树上的叶子节点保存对应的数在原序列中的位置,若某个数没出现,则赋值为inf,然后维护区间最大值。

对于操作1,可以理解为删除操作,即把相应叶子节点的值改为inf。

对于操作2,可以理解为查询这颗线段树上,[k,n+1]这些叶子节点中,第一个值大于r的节点。

做法二:主席树+set

分析题目可以发现,答案一定是在[1,n+1]这个区间内。

对于操作1,我们可以用set存哪些值是被删除了的。

对于操作2,我们先假定,没有进行过操作1,因为序列元素是1-n且每一个只会出现一次,所以我们可以得到,答案一定是a[r+1,n]中大于等于k的最小值,因为答案可能是n+1,所以我们对原序列进行扩充,第n+1个元素是n+1,然后对于每次询问,我们先找出a[r+1,n+1]中大于等于k的最小值,然后在set中二分出大于等于k的最小值,两者取min即可。

需要注意一点,这道题卡掉了2个log的做法,所以我们不能二分一个答案,然后再去查询,考虑到线段树就是一种二分结构,所以我们直接在查询的过程中进行二分。

参考代码:

/*权值线段树+二分*/
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 100;
const int inf = 0x3f3f3f3f;
int T;
int n, q;
int sum[MAXN << 2];
int a[MAXN];
void pushup(int rt)
{
    sum[rt] = max(sum[rt << 1], sum[rt << 1 | 1]);
}
void build(int l, int r, int rt)
{
    if (l == r)
    {
        sum[rt] = inf;
        return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, rt << 1);
    build(mid + 1, r, rt << 1 | 1);
    pushup(rt);
}
void update(int p, int val, int l, int r, int rt)
{
    if (l == r)
    {
        sum[rt] = val;
        return;
    }
    int mid = (l + r) >> 1;
    if (p <= mid)
        update(p, val, l, mid, rt << 1);
    else if (p > mid)
        update(p, val, mid + 1, r, rt << 1 | 1);
    pushup(rt);
}
int query_max(int l, int r, int rt, int val)
{
    if (l == r)
        return sum[rt];
    int mid = (l + r) >> 1;
    if (val <= mid)
        return query_max(l, mid, rt << 1, val);
    else
        return query_max(mid + 1, r, rt << 1 | 1, val);
}
int query(int R, int K, int l, int r, int rt)
{
    if (l == r)
        return l;
    int mid = (l + r) >> 1;
    if (K <= mid && sum[rt << 1] > R)
    {
        int p = query(R, K, l, mid, rt << 1);
        if (query_max(l, r, rt, p) > R)
            return p;
    }
    return query(R, K, mid + 1, r, rt << 1 | 1);
}
int main()
{
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d", &n, &q);
        build(1, n + 2, 1);
        for (int i = 1; i <= n; i++)
            scanf("%d", &a[i]), update(a[i], i, 1, n + 2, 1);
        int ans = 0;
        while (q--)
        {
            int op;
            scanf("%d", &op);
            if (op == 1)
            {
                int pos;
                scanf("%d", &pos);
                pos ^= ans;
                update(a[pos], inf, 1, n + 2, 1);
            }
            else
            {
                int rr, kk;
                scanf("%d%d", &rr, &kk);
                rr ^= ans;
                kk ^= ans;
                ans = query(rr, kk, 1, n + 2, 1);
                printf("%d\n", ans);
            }
        }
    }
    return 0;
}
/*主席树+set*/
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 100;
const int inf = 0x3f3f3f3f;
int T;
int n, q;
int a[MAXN];
set<int> s;
int tot, Tree[MAXN * 40], ls[MAXN * 40], rs[MAXN * 40], sum[MAXN * 40];
void update(int las, int val, int l, int r, int &rt)
{
    rt = ++tot;
    ls[rt] = ls[las];
    rs[rt] = rs[las];
    sum[rt] = sum[las] + 1;

    if (l == r)
        return;
    int mid = (l + r) >> 1;
    if (val <= mid)
        update(ls[las], val, l, mid, ls[rt]);
    else
        update(rs[las], val, mid + 1, r, rs[rt]);
}
int query(int L, int R, int l, int r, int K)
{
    if (l == r)
        return l;
    int lson = sum[ls[R]] - sum[ls[L]];
    int rson = sum[rs[R]] - sum[rs[L]];
    int mid = (l + r) >> 1;
    int res = inf;
    if (lson && K <= mid)
        res = query(ls[L], ls[R], l, mid, K);
    if (res != inf)
        return res;
    if (rson)
        res = query(rs[L], rs[R], mid + 1, r, K);
    return res;
}
int main()
{
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d", &n, &q);
        for (int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        s.clear();
        tot = 0;
        for (int i = 1; i <= n; i++)
            update(Tree[i - 1], a[i], 1, n + 1, Tree[i]);
        update(Tree[n], n + 1, 1, n + 1, Tree[n + 1]);
        int ans = 0;
        while (q--)
        {
            int op;
            scanf("%d", &op);
            if (op == 1)
            {
                int pos;
                scanf("%d", &pos);
                pos ^= ans;
                s.insert(a[pos]);
            }
            else
            {
                int R, K;
                scanf("%d%d", &R, &K);
                R ^= ans;
                K ^= ans;
                ans = query(Tree[R], Tree[n + 1], 1, n + 1, K);
                auto it = s.lower_bound(K);
                if (it != s.end())
                    ans = min(ans, *it);
                printf("%d\n", ans);
            }
        }
    }
    return 0;
}

发表留言

人生在世,错别字在所难免,无需纠正。