HDU 6703 权值线段树 + 思维

发表于 | 分类于 | 阅读次数：

题目链接

题意

给你一个序列 ，(2,r,k)代表查询从第1个数到第r个数中>= k且在这个序列中不存的数字。(1,pos)代表修改a[pos]。

思路

这个题强制在线，比赛时想用带修改莫队，发现在线后放弃了。其实这个题是查询某一段序列中大于某个数字的一个算法，我们就想应该联想到权值线段树，但是每个节点存的是这段区间中的最大下标，这样题目就转换成为了求下标大于r且这个值>= k的最小权值。初始化我们应该把每个区间的下标都最大化(比如说一开始就询问整段区间的情况)。修改操作的话我们就把那段区间的存的最大下标最大化，就代表这个区间本身的值已经不在这段区间内了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <cstring>
using namespace std;
typedef long long ll ;
const int maxn = 100005;
struct node{
   int sum;
}tr[maxn << 2];

int a[maxn];
void build(int node, int l, int r)
{
    tr[node].sum = 100005;
    if(l == r) return;
    int mid = (l + r) >> 1;
    build(node << 1, l, mid);
    build(node << 1|1, mid + 1, r);
}

void update(int node, int l, int r, int pos, int value)
{
    if(l == r && l == pos)
    {
        tr[node].sum = value;
        return;
    }
    int mid = (l + r)>> 1;
    if(pos <= mid) update(node << 1, l, mid, pos , value);
    else update(node << 1|1, mid + 1, r, pos, value);
    tr[node].sum = max(tr[node << 1].sum, tr[node << 1|1].sum);
}

int ans;
void query(int node, int l, int r, int pos, int value)
{
    if(ans != -1) return;
    if(l == r)
    {
        if(tr[node].sum > value)
        {
            ans = l;
        }
        return;
    }
    int mid = (l + r) >> 1;
    if(mid >= pos && tr[node << 1].sum > value) query(node <<1, l, mid, pos, value);
    if(tr[node << 1|1].sum > value) query(node << 1|1, mid + 1, r, pos, value);
}
int main()
{
    int T,n,q,A,b,c;
    cin >> T;
    while(T--)
    {
        scanf("%d %d",&n,&q);
        build(1,1,100001);
        for(int i = 1; i <= n; ++i)
        {
            scanf("%d",&a[i]);
            update(1,1,100001,a[i], i);
        }
        int lastans = 0;
        while(q--)
        {
            scanf("%d %d",&A,&b);
            if(A == 1)
            {
                b ^= lastans;
                update(1,1,100001, a[b],100005);
            }
            else{
                scanf("%d",&c);
                b ^= lastans;
                c ^= lastans;
                ans = -1;
                query(1,1,100001,c,b);
                cout << ans << '\n';
                lastans = ans;
            }
        }
    }
}