傲慢，凭什么傲慢
T1开幕雷击，认为水飞了”一眼CDQ板子啊“
然后十五分钟时直接开打
主要原因绝对是因为昨天场切了T1，所以飘起来了
还是应该稳重一点，起码模几个不同数据再下定论
实际上也真是水题，相当于板子了
自己对排列不够熟悉，真的没想到是直接全局-部分
正难则反？从没用上过
自以为刷题多，做题广就随便猜结论？小丑？
在这样再正式比赛时绝对会被小草绊倒，到时候就算再高都只有后悔
是什么时候开始有了这种比赛时摆烂的心态的？
有一说一，排列确实玩得不够花（比如反转，或变为\(n-P_i+1\)是等价的这样），对这些数据可以多玩一下，性质很容易出来，但光盯着题目是很难发现并运用的
这还没完
今天真的牢
下午再次遭到一次痛击
T1明明可以有很直接的做法，赛时却直接赤石，赤一堆，赤一吨
可以简化为查询序列上相对大小为1，3，2的子序列数量
想了挺多，甚至包括CDQ，实际上非常简单，而且绝对是见过的题型
可惜上一次见到时没怎么重视，好像当时赛时也是想了半天想不通
今天来做一个了断
替换：需要求一种组合的数量，这种组合由一个较小数为开头，以一个比它大的数结尾，两个数中间有一个比他们两都大的数
加上是排列，一眼可以权值线段树上操作
从后往前扫，可以求出从后面开始，直到现在为止的某一值，或给前面的数加上对应的贡献
若我们要计算到上面那个红框中的1、3、2，那么可以发现，若从后往前扫，那么计算方式就是在1处加上1
怎么让它加上1呢？
一种方式是计算这个子序列的结尾可以由多少个
一个结尾之所以能成为结尾，它前面还需要有一个过渡数，即3
所以我们实际上要求的是从2这个数字的位置开始，直到我们扫到i=(1所在的位置)这段区间中，比2大的数的个数
怎么求？方法很多，我知道的有两种：主席树，带系数线段树
因为我们要求的是在1后面，直到考虑可能计入答案的结尾位置共有多少个数比结尾位置的树大，所以最简单粗暴的方法就是先建出主席树，然后计算答案时，通过主席树计算每个结尾到当前位置这段区间上共有多少个比结尾的数大的数就行，具体实现可以是先算出不考虑i的限制，后面的数一直到位置1总共有多少个数比自己大，然后再减去位置1到i这段区间有多少个数比结尾大的总数
还有一种方法比较巧妙，
试想，如何计算一个节点前面共有多少个数比它大？是不是可以每到一个新节点，就把它后面所以比它小的数全部都加上1
但是这里有着两个约束条件：后面和比它小，这题又不能直接二位偏序，怎么办？
开一个线段树，有系数，一开始全部系数为0，然后每到一个新的结点，就把当前这个点的系数改为1
这有什么影响？若有一个在它后面，但是比它小的数，它原本也会个它加上1的，但是加了系数后，系数还是0的点就没有被更新到，巧妙，这样只会更新到位置在它后面，而且比它小的点了，因为前面的点系数仍然是0
T2是树形DP，赛时有类似的思路，但过于局限，不敢开第三维，可以将map加入DP中，这样方便存储可能DP到的gcd（了解到map是pair，虽然早已猜到）
T2赛时只要想到了开第三维，打下去了，不管是不是正解都拿了高分，应该要去尝试的，DP确确实实不熟练，确确实实见得少
T3有意思，可惜赛时没手模，这个操作确实挺能用栈模拟的，毕竟是拿出3个后，左右两边合上，这能联想到在从左往右扫时，取出栈顶露出下面的操作
数据范围更有意思，1e4的数据竟然有90分，100分是1e7，1e4->1e7是真的有难度，要高级数学知识，但是出题人不知为何设计了这样的分数，别人发现我没有，这就是分差
不过真让我来也不一定能想到DP，这个状态确实巧妙，设计了装到第i个数，剩下j个数等着匹配
转移较为显然，考虑靠近答案一下，放一个相同的再栈顶，或者是再放一个新的不同的压在栈顶，对于j=0时的特殊处理也很巧妙，赛时要想到也要时间
T4是拆成二进制得贡献，也要进行思考，在30到60分这一步还是有难度的，不过鉴于k较小，直接拆开似乎也是套路
打满暴力能拿很高分，比费尽心思切题还高，赛前总揽全局确实有意义
打暴力？换个好点的名字，抢部分分！
部分分高|还有别的部分分要拿|正解不如部分分好写|拉不开分差
那么优先抢分？
安排好顺序和做题效率同样重要，一小时写完一题高档部分分或正解似乎非常舒服
风雨欲来，保持当下，眺望远景
标签：10,系数,赛时,位置,个数,105th,2024,DP,结尾 From： https://www.cnblogs.com/tlz-place/p/18459494