[题解]-CF1567E Non-Decreasing Dilemma

Posted on Edited on In

题意

给出\(raw[]\)和两种操作:

  1. \(x\space v\), 将\(raw[x]\)修改为\(v\)
  2. \(l \space r\), 询问\(raw[l],raw[l+1],...,raw[r]\)中有多少合法的数对\((i,j)\)满足\(l \leq i \leq j \leq r\)且\(raw[i]...raw[j]\)单调不降

\(1 \leq n,q \leq 2\cdot10^5\)

题解

线段树维护区间合并. 以下\(x\)代表线段树节点标号, \(ls(x)\)和\(rs(x)\)分别代表左右儿子节点标号

容易发现对于每段长度为\(m\)的单调不降子序列, 其对答案的贡献是\(\frac{m\cdot (m+1)}2\)

建一颗线段树, 维护如下信息:

​ \(prev[x]\): 自节点\(x\)的最左端开始的最长单调不降子序列的长度

​ \(sufv[x]\): 自节点\(x\)的最右端结束的最长单调不降子序列的长度

​ \(totv[x]\): 节点\(x\)有多少合法数对\((i,j)\)满足题意

有几点细节需要注意:

  1. 对于\(prev[x]\), 只有其左儿子的\(prev[ls(x)]\)等于区间长度, 并且左儿子和右儿子的连接处不降(即\(raw[m-1] <= raw[m])\)时才有\(prev[x] = prev[ls(x)] + prev[rs(x)]\). \(sufv[]\)的维护同理

  2. 对于\(totv[x]\), 显然有\(totv[x] += totv[ls(x)] + totv[rs(x)]\). 而当其左儿子和右儿子的连接处不降时, 还需加上\(sufv[ls(x)] \cdot prev[rs(x)]\), 即新增合法区间的左端点全部从左儿子中选, 右端点全部从右儿子中选.

  3. 在统计答案时, 需要处理当前节点区间比询问区间大的情况

代码

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
//
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define int long long
mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 8e5+10;//CHANGE IT!
const int maxm = maxn*2;
const int p = 1e9+7;//CHANGE IT!
int raw[maxn];
ll Pow(ll x,ll d,ll p){ll ta=1;if(d==0)return 1%p;x %= p;ll a=Pow(x,d/2,p);ta=a*a%p;if(d%2)ta=ta*x%p;return ta%p;}
struct Segtree{
	int siz = 1;
	vector<int>prev,sufv,totv;
	void init(int n){
		while(siz < n)siz *= 2;
		prev.assign(siz*2,0);
		sufv.assign(siz*2,0);
		totv.assign(siz*2,0);
	}
	inline int ls(int x){return (x<<1)|1;}
	inline int rs(int x){return (x<<1)+2;}
	inline int f(int x){return x*(x+1)/2;}
	void pushup(int x,int lx,int rx){
		int m = (lx+rx)/2;
		int len = (rx - lx)/2;
		totv[x] = totv[ls(x)] + totv[rs(x)];
		totv[x] += (raw[m-1] <= raw[m]?sufv[ls(x)]*prev[rs(x)]:0);
		prev[x] = max(prev[ls(x)],(prev[ls(x)] == len and raw[m-1] <= raw[m])?prev[ls(x)] + prev[rs(x)]:0);
		sufv[x] = max(sufv[rs(x)],(sufv[rs(x)] == len and raw[m-1] <= raw[m])?sufv[rs(x)] + sufv[ls(x)]:0);
	}
	void Set(int idx,int v,int x,int lx,int rx){
		if(rx - lx == 1){
			raw[idx] = v;
			prev[x] = sufv[x] = totv[x] = 1;
			return;
		}
		int m = (lx+rx)/2;
		if(lx <= idx and idx < m)Set(idx,v,ls(x),lx,m);
		else Set(idx,v,rs(x),m,rx);
		pushup(x,lx,rx);
	}
	void Set(int idx,int v){
		Set(idx,v,0,0,siz);
	}
	ll cal(int l,int r,int x,int lx,int rx){
		if(l >= rx or lx >= r)return 0;
		if(l <= lx and rx <= r)return totv[x];
		int m = (lx+rx)/2;
		ll s1 = cal(l,r,ls(x),lx,m);
		ll s2 = cal(l,r,rs(x),m,rx);
		ll ans = s1+s2;
		if(raw[m-1] <= raw[m]){
			ans += max(min(m - l,sufv[ls(x)]),0LL)*max(min(r - m,prev[rs(x)]),0LL);
		}
		return ans;
	}
	ll cal(int l,int r){
		r++;
		return cal(l,r,0,0,siz);
	}
};
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.setf(ios::fixed,ios::floatfield);
	cout.precision(12);	 
	int n,q;
	Segtree seg;
	cin >> n >> q;
	for(int i = 1;i <= n;i++)raw[i] = 0;
	seg.init(n+1);
	for(int i = 1;i <= n;i++){
		int v;
		cin >> v;
		seg.Set(i,v);
	}
	while(q--){
		int opt,l,r;
		cin >> opt >> l >> r;
		if(opt == 1)seg.Set(l,r);
		else cout << seg.cal(l,r) << endl;
	}
	return 0;
}