HDU 3308 LCIS (线段树+区间合并+单点更新)
程序员文章站
2022-05-11 18:07:31
...
题意:给你N个整数,有两种操作,(1)“U A B”,表示把第A个数变成B,“Q A B”,表示查询区间[A,B]的最长连续上升序列。
题解:线段树+区间合并+单点更新
因为是连续的序列,基本的区间合并,具体操作内容可以看这篇。
有一点变动就是要求上升,我们只要判断左右子树临界点m,若x[m] < x[m + 1],那么就表示两个区间可以合并。
hdoj一直提交失败,过了样例,应该是正确的。
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<fstream>
#include<set>
#include<map>
#include<sstream>
#include<iomanip>
#define ll long long
using namespace std;
//区间合并
const int MAXN = 1e5 + 5;
int sum[MAXN << 2], lsum[MAXN << 2], rsum[MAXN << 2], x[MAXN];
struct Node {
int l, r;
int mid() { return (l + r) >> 1; }
} tree[MAXN << 2];
void PushUp(int rt) {
int m = tree[rt].mid();
sum[rt] = max(sum[rt << 1], sum[rt << 1 | 1]);
lsum[rt] = lsum[rt << 1];
rsum[rt] = rsum[rt << 1 | 1];
if (x[m] < x[m + 1]) {
if (lsum[rt] == (m - tree[rt].l + 1)) lsum[rt] += lsum[rt << 1 | 1];
if (rsum[rt] == (tree[rt].r - m)) rsum[rt] += rsum[rt << 1];
sum[rt] = max(sum[rt], rsum[rt << 1] + lsum[rt << 1 | 1]);
}
}
void build(int l, int r, int rt) {
tree[rt].l = l;
tree[rt].r = r;
if (l == r) {
sum[rt] = lsum[rt] = rsum[rt] = 1;
return;
}
int m = tree[rt].mid();
build(l, m, rt << 1);
build(m + 1, r, rt << 1 | 1);
PushUp(rt);
}
void update(int c, int pos, int rt) {
if (tree[rt].l == tree[rt].r) {
x[tree[rt].l] = c;
return;
}
int m = tree[rt].mid();
if (pos <= m) update(c, pos, rt << 1);
else update(c, pos, rt << 1 | 1);
PushUp(rt);
}
int query(int l, int r, int rt) {
if (l == tree[rt].l && r == tree[rt].r) {
return sum[rt];
}
int m = tree[rt].mid();
int res = 0;
if (r <= m) res += query(l, r, rt << 1);
else if (l > m) res += query(l, r, rt << 1 | 1);
else {
res += query(l, m, rt << 1);
res += query(m + 1, r, rt << 1 | 1);
}
return res;
}
int t, n, m, a, b;
char s[2];
int main() {
scanf("%d", &t);
while (t--) {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &x[i]);
build(1, n, 1);
while (m--) {
scanf("%s%d%d", s, &a, &b);
if (s[0] == 'U') {
update(b, a + 1, 1);
}
else {
printf("%d\n", query(a + 1, b + 1, 1));
}
}
}
return 0;
}
上一篇: Access入门教程 6.9 补充内容
下一篇: oracle 数据类型详解
推荐阅读
-
【线段树-单点更新区间最大值】hdu 1754 - I Hate It
-
HDU 1754 I Hate It【线段树】【单点更新】
-
hdu 1754 I Hate It (树状数组求区间最大和)(线段树单点修改)
-
HDU1698 Just a Hook 线段树区间更新
-
HDU1698 Just a Hook 线段树区间更新
-
HDU1698 Just a Hook (简单的区间更新线段树)
-
HDU 1540 Tunnel Warfare(线段树区间合并)
-
HDU 2871 Memory Control (线段树区间合并)
-
hdu1394Minimum Inversion Number解题报告---线段树(单点插值 & 区间逆序数求和)
-
HDU 3308 LCIS (线段树+区间合并+单点更新)