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

题目大意：

CF 1539E Game with Cards
题目大意：起始时每只手上有一张卡，值全为0，每轮会发下一张卡，可以替换左手或者右手（一定要换），使得替换完之后左右手的卡数值都在给定的范围内（每次给定的范围不同），求能否在完成n轮（2e5）后还能一直满足条件，输出满足条件的替换方法。

解：

据说是套路题，但个人感觉是很难的题。如果直接无脑去定义状态（按轮数和替换方法，或者按左右手）会发现转移非常困难，记录转移更是麻烦，问题的关键在于之前的替换手牌会影响之后这只手是否在不替换卡牌的情况下能满足条件。换句话说，只要被替换的是当前这只手，那么就可以覆盖掉之前所有的替换。所以一只手能否满足条件取决于他当前被替换的卡牌以及上一次被替换的时间，注意是时间而不是数值，因为时间是可以维护的而数值不行。
那么分类讨论，如果第n轮左手被换并且上一次右手被换是在第k轮，此时满足条件，那么说明在第k+1到n轮内，我们拿到的所有卡牌都满足左手的条件，且右手手上的第k轮拿到的卡牌在这些轮内都满足右手的条件，第一部分我们可以通过递推的方式完成，而第二部分必须每次都继承。写成公式就是dpLeft[i]=dpLeft[i-1]&&(rightrangeL<=dpRight[k]<=rightrangeR)，只要存在这个k那么dpLeft就是存在的（这里用dp加方向表示在这个方向的手上第i轮抽卡能不能满足条件）。那么显然维护的关键就在于右手的这个k了。
这个时候如果正向去维护的话是非常麻烦的，因为你永远不知道哪个k才有可能是合格的，而范围也在不断变换，这可能会造成后效性。但如果反向维护的话，就变成了维护范围，并通过范围来判断能否从i转移到k，而这个范围只要不断取交集，并用单调队列去维护就行了，由于每次转移的实质其实是靠变换方向的（因为都是从一边转移到另一边），所以答案的记录只要在遍历的同时完成就行了，是一个O(n)的神奇解法。
个人在理解上还是花了很长的时间，在做到的dp里感觉也属于是非常难了，然而大佬们都说是套路题，我哭死。
代码里其实并没有用到单调队列，因为实际上倒推的话已经没有后效性了，那么能转移的地方就可以放心转移，转移之后原来的范围限制直接归零，对于更往前的抽卡增加了容忍性，其实也包含了贪心的思想在里面，如果这步结论推出来，那么代码就是纯纯的模拟题了。

代码

代码
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

#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 998244353
#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'
using namespace std;
int l[maxn][2], r[maxn][2], c[maxn], nxt[maxn][2],wh[2],L[2],R[2];
int main() {
	cfast;
	int n,m;
	cin >> n>>m;
	wh[0] = n + 1, wh[1] = n + 1;
	inc(i, 1, n + 1) {
		cin >> c[i] >> l[i][0] >> r[i][0] >> l[i][1] >> r[i][1];
	}
	L[0] = L[1] = 0, R[0] = R[1] = m;
	int t0=1, t1=1;
	for (int i = n; i > 0; i--) {
		
		if (l[i][0] > c[i] || c[i] > r[i][0])t0 = 0;
		if (l[i][1] > c[i] || c[i] > r[i][1])t1 = 0;
		L[0] = max(L[0], l[i][1]), L[1] = max(L[1], l[i][0]);
		R[0] = min(R[0], r[i][1]), R[1] = min(R[1], r[i][0]);
		int ju0 = 0, ju1 = 0;
		if (t0 == 1 && L[0] <= c[i - 1] && c[i - 1] <= R[0])ju0 = 1;
		if (t1 == 1 && L[1] <= c[i - 1] && c[i - 1] <= R[1])ju1 = 1;
		if (ju0 == 1)nxt[i][0] = wh[0];
		if (ju1 == 1)nxt[i][1] = wh[1];
		if (ju0 == 1) {
			t1 = 1;
			wh[1] = i;
			L[1] = 0;
			R[1] = m;
		}
		if (ju1 == 1) {
			t0 = 1;
			wh[0] = i;
			L[0] = 0;
			R[0] = m;
		}
	}
	if (wh[0] > 1 && wh[1] > 1) {
		cout << "No" << endl;
		return 0;
	}
	cout << "Yes" << endl;
	int p = 1;
	if (wh[1] > 1)p = 1;
	else p = 0;
	for (int i = 1; i <= n; i = nxt[i][p], p = 1 - p) {
		//cout << "p=" << p << " next"<<i<<"."<<p<<" = " << nxt[i][p] << endl;
		inc(j, i, nxt[i][p]) {
			cout << p << " ";
		}
	}

}
/*
2022.4.27 14:46
3
1 1
3 2
2 3
*/