HDU 6406 Taotao Picks Apples【思维】【线段树】

发表于 | 更新于 | 分类于

题目大意：

现在有一个长度为n的序列，给出m个操作，每次操作都是将第p个位置处的数值替换为q，问每次操作后以第一个元素为起点的LIS的长度是多少。

解题思路：

利用线段树维护区间最大值 && 以区间左端点为起点的LIS的长度，这样答案就是以1为起点的LIS长度。对于每次查询只要替换对应位置上的值和更新树就好了，查询完后记得改回来。

有几点比较巧妙的地方稍微写一下：

  1. 区间的LIS长度 = 左子树的LIS长度 + 以左子树最大值为起点的右子树的LIS长度。
  2. 计算以某个值为起点的LIS长度时，继续比较这个值和此区间的左子树的最大值，大于等于就查询右子树，否则就返回继续查询左子树的LIS长度 + 用左子树的最大值查询右子树的LIS长度(写的很乱，直接看代码的calc函数和pushup函数好了)。

Mycode：

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 1e5+5;

int t, n, m, pos, val, a[N];

struct node
{
    int l, r;
    int maxx, val;
} tree[N<<2];

int calc(int val, int rt)
{
    if(tree[rt].l == tree[rt].r)
        return val < tree[rt].maxx;
    if(tree[rt<<1].maxx <= val)
        return calc(val, rt<<1|1);
    else
        return calc(val, rt<<1) + (tree[rt].val - tree[rt<<1].val);
}

void pushup(int rt)
{
    tree[rt].maxx = max(tree[rt<<1].maxx, tree[rt<<1|1].maxx);
    tree[rt].val = tree[rt<<1].val + calc(tree[rt<<1].maxx, rt<<1|1);
}

void build(int l, int r, int rt)
{
    tree[rt].l = l;
    tree[rt].r = r;
    if(l == r)
    {
        tree[rt].maxx = a[l];
        tree[rt].val = 1;
        return ;
    }
    int mid = l + r >> 1;
    build(l, mid, rt << 1);
    build(mid + 1, r, rt << 1 | 1);
    pushup(rt);
}

void update(int pos, int val, int rt)
{
    if(tree[rt].l == tree[rt].r)
    {
        tree[rt].maxx = val;
        return ;
    }
    int mid = tree[rt].l + tree[rt].r >> 1;
    if(pos <= mid)
        update(pos, val, rt<<1);
    else
        update(pos, val, rt<<1|1);
    pushup(rt);
}

int main()
{
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= n; ++i)
            scanf("%d", &a[i]);
        build(1, n, 1);
        while(m--)
        {
            scanf("%d%d", &pos, &val);
            update(pos, val, 1);
            printf("%d\n", tree[1].val);
            update(pos, a[pos], 1);
        }
    }
    return 0;
}
Donate comment here
0%