D. Omkar and Medians——Codeforces Round #724 (Div. 2)

https://codeforces.com/contest/1536/problem/D

这个又是往状态转移想，dp思路cd很常见！
下一个状态，只能改变最多一个排位也一定可以改变一个排位。
所以只要贪心，看上一个状态到当前是否可以即可，即不是到不了，更好判断。

还有知识点：
set是有序的
$next(p)$和$prev(p)$函数会返回p的下一个/上一个指针。

一个小技巧：
墙：用INF和-INF，不用特判

一个小bug：
注意不要找到flag就习惯性break，以读完。紫书就提过这个细节。

附：和ssjiels的对话：

出尘 0:21:29
slsls

出尘 0:30:02
我想问一下昨天晚上的div2D是怎么想到的

ssjiels 0:30:37
凭直觉

ssjiels 0:30:52
两个数只能改变一次排位

出尘 0:31:02

出尘 0:31:34
嗯！

ssjiels 0:31:50
算是一种经验？

出尘 0:32:27

出尘 0:32:41
太厉害了

ssjiels 0:33:45
分析的话就是，看下加两个数之后中位数能怎么变吧

ssjiels 0:34:02
要么中位数移到附近，要么不变

出尘 0:34:28
嗯

出尘 0:34:48
有道理！

出尘 0:35:16
比英文题解的一长串要好理解多了w

出尘 0:35:57
但是可能是写的少吧，很难想到

出尘 0:36:00

ssjiels 0:36:30
多写就好了

真的sls几句话就懂了，div2d欸 ^ _ ^
所以最后的结果是：

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
int main(){
    int t;scanf("%d",&t);int n;while(t--){
    scanf("%d",&n);set<int>s;s.insert(INF);s.insert(-INF);bool flag=true;int te;scanf("%d",&te);s.insert(te);auto p=s.find(te);for(int i=1;i<n;i++){
    scanf("%d",&te);if(te>*next(p)||te<*prev(p)){
    flag=false;//break;不可以，还要读完！ }s.insert(te);p=s.find(te);}printf("%s\n",(flag?"YES":"NO"));}return 0;
}