洛谷P1531《I Hate It》

八月 05, 2018 5042

暴力能过的线段树板子题

题目背景

很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。这让很多学生很反感。

题目描述

不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩

Input / Output 格式 & 样例

输入格式

第一行，有两个正整数 N 和 M ( 0<N<=200000,0<M<5000 )，分别代表学生的数目和操作的数目。

学生ID编号分别从1编到N。

第二行包含N个整数，代表这N个学生的初始成绩，其中第i个数代表ID为i的学生的成绩。

接下来有M行。每一行有一个字符 C (只取’Q’或’U’) ，和两个正整数A，B。

当C为’Q’的时候，表示这是一条询问操作，它询问ID从A到B(包括A,B)的学生当中，成绩最高的是多少。

当C为’U’的时候，表示这是一条更新操作，如果当前A学生的成绩低于B，则把ID为A的学生的成绩更改为B，否则不改动。

输出格式

对于每一次询问操作，在一行里面输出最高成绩

输入输出样例

输入样例：

1
2
3
4
5
6
7
8
5 6
1 2 3 4 5
Q 1 5
U 3 6
Q 3 4
Q 4 5
U 2 9
Q 1 5

输出样例：

1
2
3
4
5
6
5
9

解题思路

单点修改，区间查询 ……

线段树 树状数组！

对了，注意处理输入，含读入char的题目最好不要用快读 ……

别问我怎么知道的

线段树解法

可以说是很裸的一道题了

只需要单点修改，lazyTag什么的不需要的

就简单把区间和查询改成区间最值查询就行了

代码实现

线段树解法

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
using namespace std;

const int MAXN = 200000 + 10;

int a[MAXN], segt[MAXN * 4];
int n, m;

inline int leftChild(int x) {
    return x << 1;
}

inline int rightChild(int x) {
    return x << 1 | 1;
}

inline void pushUp(int root) {
    segt[root] = std::max(segt[leftChild(root)], segt[rightChild(root)]);
    // 更新最大值
}

inline void buildTree(int l, int r, int root) {
    if (l == r) {
        segt[root] = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    buildTree(l, mid, leftChild(root));
    buildTree(mid + 1, r, rightChild(root));
    pushUp(root);
}

inline int query(int l, int r, int ql, int qr, int root) {
    int res = -2147483640;
    if (ql <= l && r <= qr) return segt[root];
    int mid = (l + r) >> 1;
    if (ql <= mid) res = std::max(res, query(l, mid, ql, qr, leftChild(root)));
    if (mid < qr) res = std::max(res, query(mid + 1, r, ql, qr, rightChild(root)));
    // 查询最大值
    return res;
}

inline void Modify(int l, int r, int dest, int root, int k) {
    if (l == r) {
        segt[root] = std::max(segt[root], k);
        return;
    }
    int mid = (l + r) >> 1;
    if (dest <= mid) Modify(l, mid, dest, leftChild(root), k);
    if (mid < dest) Modify(mid + 1, r, dest, rightChild(root), k);
    pushUp(root);
}

inline int getint() {
    int s = 0, x = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') x = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    return s * x;
}

inline void putint(int x, bool returnValue) {
    if (x < 0) {
        x = -x;
        putchar('-');
    }
    if (x >= 10) putint(x / 10, false);
    putchar(x % 10 + '0');
    if (returnValue) putchar('\n');
}

int main(int argc, char *const argv[]) {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    buildTree(1, n, 1);
    for (int i = 1; i <= m; ++i) {
        char op;
        int a, b;
        cin >> op >> a >> b;
        // 推荐使用std::cin！
        switch(op) {
            case 'Q': {
                putint(query(1, n, a, b, 1), true);
                break;
            }
            case 'U': {
                Modify(1, n, a, 1, b);
                break;
            }
        }
    }
    return 0;
}

暴力代码

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
using namespace std;

const int MAXN = 200000 + 10;

int segt[MAXN]; 
int n, m;

inline int getint() {
	int s = 0, x = 1;
	char ch = getchar();
	while (!isdigit(ch)) {
		if (ch == '-') x = -1;
		ch = getchar();
	}
	while (isdigit(ch)) {
		s = s * 10 + ch - '0';
		ch = getchar();
	}
	return s * x;
}

inline void putint(int x, bool returnValue) {
	if (x < 0) {
		x = -x;
		putchar('-');
	}
	if (x >= 10) putint(x / 10, false);
	putchar(x % 10 + '0');
	if (returnValue) putchar('\n');
}

inline int query(int l, int r) {
	int res = -2147483640;
	for (int i = l; i <= r; ++i) res = std::max(res, segt[i]);
	return res;
}

inline void Modify(int r, int k) {
	segt[r] = std::max(segt[r], k);
}

int main(int argc, char *const argv[]) {
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) cin >> segt[i];
	for (int i = 1; i <= n; ++i) cout << segt[i] << ' ';
	cout << endl;
	for (int i = 1; i <= m; ++i) {
		char op;
		int a, b;
		cin >> op >> a >> b;
		switch(op) {
			case 'Q': {
				cout << query(a, b) << endl;
				break;
			}
			case 'U': {
				Modify(a, b);
				break;
			}
		}
	}
	return 0;
}