Codeforces Round #742 (Div. 2) E. Non-Decreasing Dilemma（线段树）

题目链接

题目大意

给你一个长度为 n n n 的数组 a a a
每次有两种操作
1   x   y : a x = y 1 \ x\ y: a_x = y 1 x y:ax​=y
2   l   r : 2 \ l \ r: 2 l r: 问你区间 [ l , r ] [l, r] [l,r] 内有多少对 ( p , q ) , l ≤ p ≤ q ≤ r (p, q), l \leq p \leq q \leq r (p,q),l≤p≤q≤r 满足子序列 a p ≤ a p + 1 ≤ ⋯ ≤ a q a_p \leq a_{p+1} \leq \cdots \leq a_q ap​≤ap+1​≤⋯≤aq​

解题思路

与这道题的思路很相似
线段树一个节点，维护了节点答案 s u m sum sum，紧靠左端点的最长不降子序列的长度 l e n l lenl lenl，紧靠右端点的最长不降子序列长度 l e n r lenr lenr，线段树区间长度 s z sz sz。
考虑如何更新
l e n l : lenl: lenl: 首先继承左子树的 l e n l lenl lenl，如果左子树的 l e n l lenl lenl 等于左子树的 s z sz sz，且左子树的右端点的值不超过右子树的左端点的值，那么 l e n l lenl lenl 再加上右子树的 l e n l lenl lenl （这说明左右子树在中间可以拼起来）
l e n l = t l . l e n l + ( t l . l e n l = = t l . s z   & &   a [ t l . r ] ≤ a [ t r . l ]   ?   t r . l e n l : 0 ) lenl = tl.lenl + (tl.lenl == tl.sz \ \&\&\ a[tl.r] \leq a[tr.l] \ ?\ tr.lenl : 0) lenl=tl.lenl+(tl.lenl==tl.sz && a[tl.r]≤a[tr.l] ? tr.lenl:0)
l e n r lenr lenr 同上
l e n r = t r . l e n r + ( t r . l e n r = = t r . s z   & &   a [ t l . r ] ≤ a [ t r . l ]   ?   t l . l e n r : 0 ) lenr = tr.lenr + (tr.lenr == tr.sz \ \&\&\ a[tl.r] \leq a[tr.l] \ ? \ tl.lenr : 0) lenr=tr.lenr+(tr.lenr==tr.sz && a[tl.r]≤a[tr.l] ? tl.lenr:0)
s u m : sum: sum:
首先 s u m sum sum 等于左子树的 s u m sum sum 与右子树的 s u m sum sum 之和。如果左子树的右端点的值不超过右子树的左端点的值，那么 l e n l lenl lenl 再加上右子树的 l e n l lenl lenl （这说明左右子树在中间可以拼起来），那么我们还要加上左子树的 l e n r lenr lenr 乘以 右子树的 l e n l lenl lenl。
s u m = t l . s u m + t r . s u m + ( a [ t l . r ] ≤ a [ t r . l ]   ?   t l . l e n r ∗ t r . l e n l : 0 ) sum = tl.sum + tr.sum + (a[tl.r] \leq a[tr.l] \ ?\ tl.lenr * tr.lenl : 0) sum=tl.sum+tr.sum+(a[tl.r]≤a[tr.l] ? tl.lenr∗tr.lenl:0)
还有一个要注意的点是，我们在 q u e r y query query 的时候，需要返回一个线段树的节点，这是因为答案不仅受到左右节点的 s u m sum sum 的影响，还会受到该节点的其他值的影响。

Code

#include <bits/stdc++.h>
#define ll long long
#define qc ios::sync_with_stdio(false); cin.tie(0);cout.tie(0)
#define fi first
#define se second
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define pb push_back
using namespace std;
const int MAXN = 2e5 + 7;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
int n, q;
int a[MAXN];
struct Tree{
	int l, r;
	int lenl, lenr;
	ll sum;
	int sz; 
}tree[MAXN << 2];
Tree operator + (Tree x, Tree y){
	Tree ret;
	ret.sz = x.sz + y.sz;
	ret.l = x.l;
	ret.r = y.r;
	ret.sum = x.sum + y.sum + (a[x.r] <= a[y.l] ?  1ll * x.lenr * y.lenl : 0);
	ret.lenl = x.lenl + (x.lenl == x.sz && a[x.r] <= a[y.l] ? y.lenl : 0);
	ret.lenr = y.lenr + (y.lenr == y.sz && a[x.r] <= a[y.l] ? x.lenr : 0);
	return ret;
}
void pushup(int rt){
	tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];
}
void build(int l, int r, int rt){
	tree[rt].l = l;
	tree[rt].r = r;
	if(l == r){
		tree[rt].lenl = tree[rt].lenr = 1;
		tree[rt].sum = 1;
		tree[rt].sz = 1;
		return ;
	}
	int m = (l + r) >> 1;
	build(l, m, rt << 1);
	build(m+1, r, rt << 1 | 1);
	pushup(rt);
}
void update(int pos, int x, int rt){
	if(tree[rt].l == tree[rt].r){
		return ;
	}
	int m = (tree[rt].l + tree[rt].r) >> 1;
	if(pos <= m)
		update(pos, x, rt << 1);
	else
		update(pos, x, rt << 1 | 1);
	pushup(rt);
}
Tree query(int L, int R, int rt){
	if(L <= tree[rt].l && tree[rt].r <= R)
		return tree[rt];
	int m = (tree[rt].l + tree[rt].r) >> 1;
	if(L > m){
		return query(L, R, rt << 1 | 1);
	}
	else if(R <= m){
		return query(L, R, rt << 1);
	}
	else{
		return query(L, R, rt << 1) + query(L, R, rt << 1 | 1);
	}
}
void solve(){
    cin >> n >> q;
	for (int i = 1; i <= n; ++i){
	    cin >> a[i];
	}
	build(1, n, 1);
	while(q--){
		int t, l, r;
		cin >> t >> l >> r;
		if(t == 1){
			a[l] = r;
			update(l, r, 1);

		}
		else{
			cout << query(l, r, 1).sum << "\n";
		}
	}
}

int main()
{
    #ifdef ONLINE_JUDGE
    #else
       freopen("in.txt", "r", stdin);
       freopen("out.txt", "w", stdout);
    #endif

    qc;
    int T;
    //cin >> T;
    T = 1;
    while(T--){

        solve();
    }
    return 0;
}