题目链接:http://codeforces.com/problemset/problem/1567/E
题目大意:
有一个长度为 \(n\) 的数列 \(a\),你需要对其进行 \(q\) 次操作,操作有两种类型,按如下格式给出:
1 x y
:将 \(a_x\) 变成 \(y\)。2 l r
:询问位置在 \([l,r]\) 之间的不下降子串有多少个。形式化地说,你需要求出满足下列条件的数对 \((p,q)\) 的个数:- \(l\leqslant p\leqslant q\leqslant r\)。
- \(\forall i\in[p,q),a_i\leqslant a_{i+1}\)。
解题思路:
维护一棵线段树,需要记录:
- 区间左端点的数值
- 区间右端点的数值
- 区间左端点开始的最长连续非严格上升子序列长度
- 区间又断电开始的最长连续非严格上升子序列长度
- 区间内连续非严格上升子序列个数
查询的时候先统计左子树和右子树各自的非严格上升子序列个数,然后左右子树汇总。就能解决这个问题。
示例程序:
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int n, q;
int lp[maxn<<2], // 最左边节点权值
rp[maxn<<2], // 最右边节点权值
llen[maxn<<2], // 最左边连续一段长度
rlen[maxn<<2]; // 最右边连续一段长度
long long tr[maxn<<2]; // 区间内连续上升子序列个数
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1
void push_up(int l, int r, int rt) {
lp[rt] = lp[rt<<1];
rp[rt] = rp[rt<<1|1];
int mid = (l + r) / 2;
llen[rt] = llen[rt<<1];
if (llen[rt<<1] == mid - l + 1 && rp[rt<<1] <= lp[rt<<1|1])
llen[rt] += llen[rt<<1|1];
rlen[rt] = rlen[rt<<1|1];
if (rlen[rt<<1|1] == r - mid && rp[rt<<1] <= lp[rt<<1|1])
rlen[rt] += rlen[rt<<1];
tr[rt] = tr[rt<<1] + tr[rt<<1|1];
if (rp[rt<<1] <= lp[rt<<1|1])
tr[rt] += (long long) rlen[rt<<1] * llen[rt<<1|1];
}
void build(int l, int r, int rt) {
if (l == r) {
scanf("%d", lp+rt);
rp[rt] = lp[rt];
llen[rt] = rlen[rt] = tr[rt] = 1;
return;
}
int mid = (l + r) / 2;
build(lson);
build(rson);
push_up(l, r, rt);
}
void update(int p, int v, int l, int r, int rt) {
if (l == r) {
lp[rt] = rp[rt] = v;
// llen[rt] = rlen[rt] = tr[rt] = 1; // 叶子节点这三个值不会改变
return;
}
int mid = (l + r) / 2;
(p <= mid) ? update(p, v, lson) : update(p, v, rson);
push_up(l, r, rt);
}
long long query(int L, int R, int l, int r, int rt) {
if (L <= l && r <= R) return tr[rt];
int mid = (l + r) / 2;
long long res = 0;
if (L <= mid) res += query(L, R, lson);
if (R > mid) res += query(L, R, rson);
if (L <= mid && R > mid && rp[rt<<1] <= lp[rt<<1|1]) {
int lcnt = min(rlen[rt<<1], mid - L + 1);
int rcnt = min(llen[rt<<1|1], R - mid);
res += (long long) lcnt * rcnt;
}
return res;
}
int main() {
scanf("%d%d", &n, &q);
build(1, n, 1);
while (q--) {
int op, x, y;
scanf("%d%d%d", &op, &x, &y);
if (op == 1)
update(x, y, 1, n, 1);
else
printf("%lld\n", query(x, y, 1, n, 1));
}
return 0;
}
标签:Non,Dilemma,int,题解,线段,序列,端点,区间,leqslant
From: https://www.cnblogs.com/quanjun/p/17118046.html