题目
题意：给定一个长度为
n
n
n的数组
a
i
a_i
ai，有两种操作
o
p
,
x
,
y
op,x,y
op,x,y，当
o
p
op
op取1时，表示把
a
x
a_x
ax更新为
y
y
y；当
o
p
op
op取2时，表示查询区间
[
x
,
y
]
[x,y]
[x,y]存在多少子区间
[
l
,
r
]
,
x
<
=
l
,
r
<
=
y
[l,r],x<=l,r<=y
[l,r],x<=l,r<=y使得区间
[
l
,
r
]
[l,r]
[l,r]满足
a
l
<
=
a
l
+
1
<
=
.
.
.
<
=
a
r
−
1
<
=
a
r
a_l<=a_{l+1}<=...<=a_{r-1}<=a_r
al<=al+1<=...<=ar−1<=ar
官方、参考
思路：线段树，维护最长前后缀、合法子区间数量、以及标记当前区间是否非递减。代码有注释，详见代码。
记录今日份憨憨，卡了好几个小时debug…
num[rt] = num[rson] + (canCombine ? 0 : f(pre[rson]));
该语句一开始忘记加括号了，+号运算符优先级高于?，错误写法如下：
num[rt] = num[rson] + canCombine ? 0 : f(pre[rson]);
AC 代码
#includeusing namespace std; #define ll long long const int maxn = 200010; #define lson (rt << 1) #define rson (rt << 1 | 1) bool isIn[maxn << 2];// 标记当前区间是否是非递减的 ll pre[maxn << 2];// 记录最长非递减前缀长度 ll suf[maxn << 2];// 记录最长非递减后缀长度 ll num[maxn << 2];// 记录除了pre和suf之外的 非递减 的区间个数 int a[maxn]; int n, q, k; #define debug 0 ll f(ll x) { return x * (x + 1) / 2; } #define oj #ifdef oj void pushup(int rt, int l, int r) { int m = (l + r) / 2; bool canCombine = a[m] <= a[m+1]; // 更新isIn if (isIn[lson] && isIn[rson] && canCombine) { isIn[rt] = 1;// 当前仅当左右孩子都连续，且可以拼接 } else { isIn[rt] = 0; } // 更新pre pre[rt] = pre[lson]; if (isIn[lson] && canCombine) pre[rt] += pre[rson]; // 更新suf suf[rt] = suf[rson]; if (isIn[rson] && canCombine) suf[rt] += suf[lson]; if (debug) { if (l == 1 && r == 2) { printf("lson(%d, %d) (%d %lld %lld %lld)n", l, m, isIn[lson], pre[lson], suf[lson], num[lson]); printf("rson(%d, %d) (%d %lld %lld %lld)n", m + 1, r, isIn[rson], pre[rson], suf[rson], num[rson]); } } // 更新num if (isIn[lson] && isIn[rson]) {// 左右孩子连续，取0 num[rt] = 0; } else if (isIn[lson]) {// 左孩子连续，取右孩子 num[rt] = num[rson] + (canCombine ? 0 : f(pre[rson])); } else if (isIn[rson]) {// 右孩子连续，取左孩子 num[rt] = num[lson] + (canCombine ? 0 : f(suf[lson])); } else {// 否则 取左右孩子 num[rt] = num[lson] + num[rson]; num[rt] += canCombine ? f(suf[lson] + pre[rson]) : f(suf[lson]) + f(pre[rson]); } } #else void pushup(int rt, int l, int r) {// 对拍 isIn[rt] = 0; num[rt] = num[lson] + num[rson]; int m = (l + r) / 2; if (a[m] <= a[m+1]) { if (isIn[lson] && isIn[rson]) pre[rt] = suf[rt] = suf[lson] + pre[rson], isIn[rt] = 1; else if (isIn[lson]) pre[rt] = suf[lson] + pre[rson], suf[rt] = suf[rson]; else if (isIn[rson]) suf[rt] = suf[lson] + pre[rson], pre[rt] = pre[lson]; else pre[rt] = pre[lson], suf[rt] = suf[rson], num[rt] += f(suf[lson] + pre[rson]); } else { pre[rt] = pre[lson], suf[rt] = suf[rson]; if (isIn[lson] && !isIn[rson]) num[rt] += f(pre[rson]); else if (isIn[rson] && !isIn[lson]) num[rt] += f(suf[lson]); else if (!isIn[lson] && !isIn[rson]) num[rt] += f(suf[lson]) + f(pre[rson]); } } #endif void build(int rt, int l, int r) { if (l == r) { scanf("%d", &a[l]); isIn[rt] = 1; pre[rt] = suf[rt] = 1; num[rt] = 0; return; } int m = (l + r) / 2; build(lson, l, m); build(rson, m + 1, r); pushup(rt, l, r); } void update(int rt, int l, int r, int x, int y) { if (l == r) { a[x] = y; return; } int m = (l + r) / 2; if (x <= m) update(lson, l, m, x, y); else update(rson, m + 1, r, x, y); pushup(rt, l, r); } ll query(int rt, int l, int r, int x, int y) { if (r < x || l > y) return 0; ll res = 0; if (l >= x && r <= y) { if (debug) { if (x == 8 && y == 10 || x == 7 && y == 9) printf("(%d (%d, %d))isIn: %d pre: %lld suf: %lld num %lldn", rt, l, r, isIn[rt], pre[rt], suf[rt], num[rt]); } bool canCombine = a[l] >= a[l-1]; if (isIn[rt]) {//整段都非递减 if (canCombine) {// 衔接上一段 k += (r - l + 1); } else { res += f(k); k = (r - l + 1); } } else {// 整段不是非递减 res += num[rt]; res += canCombine ? f(k + pre[rt]) : f(k) + f(pre[rt]); k = suf[rt]; } return res; } int m = (l + r) / 2; res += query(lson, l, m, x, y); res += query(rson, m + 1, r, x, y); return res; } int main() { scanf("%d%d", &n, &q); build(1, 1, n); while (q--) { int op, x, y; scanf("%d%d%d", &op, &x, &y); if (op == 1) { update(1, 1, n, x, y); } else { k = 0;// 用于维护当前非递减序列的长度 printf("%lldn", query(1, 1, n, x, y) + f(k)); } } return 0; }
