把过去和现在的笔记记录也搬了过来，也算是给以后留个念想吧，想想一开始打acm就是图一乐，后来发现这游戏还挺上头的，也算是度过了一段电竞生涯（xs）
早些时候的笔记写的好中二，连我自己看着都羞耻。
不过，就喜欢这种羞耻的感觉。
收录的题目大部分是个人认为质量不错的题目，以DP为主，非DP的题目都用※进行了标识。
当然，有些题解思路本身也是源自其他人的，不过除非特殊标注，否则都是用的自己的代码。

题目大意：

CF 1550C
题目大意：太烦了，转移过来就是对于一个数组(2e5)，求其中合格的子段数，子段长度<=2时子段一定合格，否则必须在该子段中没有长度>=3的不下降子序列或者不上升子序列。

解：

面对这个题，最先想到的显然就是离散化+权值线段树，于是理所当然地这么做了。
由于要求长度为3，换句话说我要在每个i之前找到一个最大的下标，使得该下标时存在长度>=3的不下降或不上升子序列，这个下标+1对应的位置就是我从这个i能达到的最远位置——并不是，如果能达到的最远位置是dp[i]，那么dp[i]=max(刚刚那个位置,dp[i-1])，这个很容易就能理解。
于是进一步转化，其实相当于就是求，对于每个i，假如upper[i]表示大于等于i的最近一个数的位置，lower[i]表示小于等于，那么每个i的“那个位置”实则就是max(upper[k],lower[j])，其中k>=i而j<=i，这之中我们需要求两个区间最值：一个大于等于一个大于等于i的数的数最后出现的位置，和一个小于等于一个小于等于i的数的数最后出现的位置（大雾）。然后我们需要三个权值线段树来解决这个问题：一个记录一个数最后出现的位置，一个记录大于等于一个数的数最后出现的位置，一个记录小于等于一个数的数最后出现的位置，然后对于每个i，先处理用第一棵线段树解决出后两个数的数值，接着用后两棵树来求出dp[i]，然后再用第一棵树求出的两个数值来更新后两棵树的新的值，把常数化简到最后可以每个i只进行6次区间操作，也就是O(6nlog)的复杂度，以及三棵线段树的空间复杂度。
非常骄傲地花一个半小时解决了这道C题。
然后看题解，发现了对于任何序列有一个规律：长度为2N+1的序列中，必定存在一个长度至少为N+1的不上升或不下降子序列，所以对于本题N=2来讲，长度大于等于5的子段一定是存在一个长度为3的不合格序列的，那么对于每个下标只要遍历到长度为4的段长就行了。
每天一个ACM小常识。
做完这题感觉权值线段树力又提升了，好耶。

代码

代码
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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <istream>
#include <map>
#include <cmath>
#include <stack>
#include <set>
#include <cstring>
#include <string>
#include <fstream>
#define ll long long
#define maxn 200005
#define mdl 1000000007
#define clr(a,n) for(int i=0;i<n;i++)a[i]=0
#define cfast std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pll pair<ll,ll>
#define pii pair<int,int>
#define inc(i,a,n) for(int i=a;i<n;i++)
#define vset(a,n,m) for(int i=0;i<n;i++)a[i]=m;
#define endl '\n'
#define pi 3.141592657
using namespace std;
ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	if (b == 0)return a;
	return gcd(b, a % b);
}
ll cpow(ll x, ll n) {
	ll ans = 1;
	while (n > 0) {
		if (n & 1) ans = (ans * x) % mdl;
		x = (x * x) % mdl;
		n >>= 1;
	}
	return ans;
}
ll tree[maxn * 4][3];
void addq(int o, int l, int r, ll x, int ql, int qr,int type) {
	if (ql <= l && r <= qr) {
		tree[o][type] = max(tree[o][type], x);
		return;
	}
	int m = (l + r) / 2;
	int ls = 2 * o, rs = 2 * o + 1;
	if (ql <= m)addq(ls, l, m, x, ql, qr,type);
	if (m < qr)addq(rs, m + 1, r, x, ql, qr,type);
	tree[o][type] = max(tree[ls][type], tree[rs][type]);
}
ll query(int o, int l, int r, int ql, int qr,int type) {
	if (ql <= l && r <= qr) {
		return tree[o][type];
	}
	int m = (l + r) / 2;
	int ls = 2 * o, rs = 2 * o + 1;
	ll ret = 0;
	if (ql <= m)ret = query(ls, l, m, ql, qr,type);
	if (m < qr)ret = max(ret, query(rs, m + 1, r, ql, qr,type));
	return ret;
}
ll c[maxn], a[maxn];
int lsh(int n)
{
	sort(c, c + n);
	int cnt = unique(c, c + n) - c;
	for (int i = 1 ;i <= n; i++)
		a[i] = lower_bound(c, c + cnt, a[i]) - c + 1;
	return cnt;
}
ll lower[maxn],upper[maxn], dp[maxn];
int main() {
	cfast;
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		inc(i, 1, n+1) {
			cin >> a[i];
			c[i-1] = a[i];
		}
		int cnt=lsh(n);
		inc(i, 1, 4 * cnt + 1) {
			tree[i][1] = 0;
			tree[i][0] = 0;
			tree[i][2] = 0;
		}
		inc(i, 1, cnt+1) {
			lower[i] = 0;
			upper[i] = 0;
			dp[i] = max(1, i - 1);
		}
		ll ans = 0;
		inc(i, 1, n + 1) {
			ll low = query(1, 1, cnt, 1, a[i],0);
			ll up = query(1, 1, cnt, a[i], cnt, 0);
		//	cout << "lower of " << i << " = " << low << endl;
		//	cout << "upper of " << i << " = " << up << endl;
			
			addq(1, 1, cnt, i, a[i], a[i],0);
		/*	inc(k, 1, cnt + 1) {
				cout << query(1, 1, cnt, k, k, 0) << " ";
			}cout << endl;*/
	
			lower[i] = low;
			upper[i] = up;
			ll d1 = query(1, 1, cnt, 1, a[i], 1);
			ll d2 = query(1, 1, cnt, a[i], cnt, 2);
			addq(1, 1, cnt, low, a[i], a[i], 1);
			addq(1, 1, cnt, up, a[i], a[i], 2);
			
			dp[i] = max(max(d1, d2) + 1,dp[i-1]);
		//	cout << "dp." << i << " = " << dp[i] << endl;
			ans += i - dp[i] + 1;
		}
		cout << ans << endl;
	}
}
/*
2022.5.2 13:53
1 5
6 9 1 9 6
*/