BZOJ1012 [JSOI2008]最大数maxnumber

BZOJ1012

区间查询,单点修改,显然可以用线段树处理。

设线段树根节点覆盖的区间为[1,200000],直接操作即可。

也可使用单调栈或单调队列,效率比线段树更优,可参考hzwer的文章


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
#include <cstdio>
#include <cctype>
#include <algorithm>


const int N = 200000;


int val[4 * N + 10];


void amend(int , int , int , int , int );
int query(int , int , int , int , int );
int read(void);


int main(void)
{
    for (int m = read(), d = read(), cur = 1, lst = 0; m--; )
    {
        char x;
        while (!isupper(x = getchar()))
            ;
        int y = read();
        if (x == 'A')
            amend(1, 1, N, cur++, (y + lst) % d);
        else
            printf("%d\n", lst = query(1, 1, N, cur - y, cur));
    }
    return 0;
}


void amend(int rt, int l, int r, int x, int v)
{
    if (l == r - 1)
    {
        val[rt] = v;
        return ;
    }
    if (x < (l + r) / 2)
    {
        amend(rt * 2, l, (l + r) / 2, x, v);
        val[rt] = std::max(val[rt], val[rt * 2]);
    }
    else
    {
        amend(rt * 2 + 1, (l + r) / 2, r, x, v);
        val[rt] = std::max(val[rt], val[rt * 2 + 1]);
    }
}


int query(int rt, int l, int r, int L, int R)
{
    if (L <= l && r <= R)
        return val[rt];
    int ret = 0;
    if (L < (l + r) / 2)
        ret = std::max(ret, query(rt * 2, l, (l + r) / 2, L, R));
    if ((l + r) / 2 < R)
        ret = std::max(ret, query(rt * 2 + 1, (l + r) / 2, r, L, R));
    return ret;
}


inline int read(void)
{
    char x;
    while (!isdigit(x = getchar()))
        ;
    int num = x - '0';
    while (isdigit(x = getchar()))
        (num *= 10) += x - '0';
    return num;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注