平淡无奇的笔记
暂且就先将所有笔记写在一篇博客上吧，等需要分类管理的时候再分成多个博客放到一个专题中。
目录
状态相关与无关（CF915C Permute Digits）
1. 树状数组、线段树，ST表的应用场景：区间和、区间 gcd 、最大子段和 等 满足结合律且支持快速合并
2. 能用vis数组尽量不用set，复杂度会加log且常数较大
同时保留原始顺序与有序顺序的方法
最近突然做到很多有关此类问题的题目，有必要分离出来讲。
1.对于问题有序且需要获取序列顺序信息的算法，可用结构体标记元素下标，相当于指向原位置，再对序列进行顺序变换即可，不会丢失原位置信息。（本质是排序）
2. 当序列为排列且元素范围较小时，还可用数组pre[i]=j表示数字i的原始位置为j，相当于指向原位置，相比于方法1的优点是通过元素值查询和更新的复杂度为O(1)（本质是计数）
分组问题
1. 01分组问题，经常考虑个数相同或不相同，这样想：n个0和1的配对，剩下要不是1要不是0，有m个，执行算法后01个数的和或差要满足什么条件，要使m=0需要怎么操作，等等（#741 (Div. 2)D1、#740 (Div. 2, based on VK Cup 2021 - Final (Engine)B）。
2. 对数字分组，每组都不存在相同的数，可对序列排序，再间隔组数选数即可。（相同数字个数要少于组数）（CF1551B2 Wonderful Coloring - 2）
3. 对数字分组，每组都是相同的数，可对序列排序，再连续选数即可。（CF1203B Equal Rectangles）
状态相关与无关（CF915C Permute Digits）
1. 当初考虑从左到右遍历b串，对每个位置从a中从大到小找到第一个小于等于这个位置上的数，错误在于当前选择的数（状态）会影响之后的选择，也就是说选了一个数字后后续的遍历就无法选择这个数字，称为状态相关。当且仅当后续的遍历不再需要考虑这个数字时算法正确，称为状态无关。
问题的有序无序性
1. 分析问题时发现序列的排列与答案无关，问题不涉及顺序，常考虑进行排序或对相同元素计数。 （CF706B Interesting drink）
2. 分析问题时发现序列的排列与答案有关，问题涉及顺序，数据范围较小且不重复，可采用值与下标身份交换的存储方式，适合处理元素位置多次交换的问题，只需改变值，不需要改变位置（HDU 1394 Minimum Inversion Number）
答案的唯一性
善用反证法，容易证明某些题目的答案必须包含某个性质，从而只有一种可能。
例1：观察到运动员获得金牌必须战胜所有运动员，存在战胜与被战胜的关系。假设有两个运动员得金牌，可知两个运动员互相战胜，矛盾说明只有一个运动员，或者获得金牌的运动员不存在。
例2：观察到点权小于所有所连点会被删除，假设有两个幸存者，可知两个幸存者的点权都不小于对方，即点权相等，与题意矛盾，所以只有一个幸存者。
鸽笼原理
Educational Codeforces Round 111 (Rated for Div. 2) C Manhattan Subarrays
when either ai≤aj≤ak or ai≥aj≥ak. In other words, subarray is bad if and only if it contains either non-decreasing subsequence of length 3&nbs***on-increasing subsequence of length 3.Any sequence of length at least 5 contains either non-decreasing or non-increasing subsequence of length 3.
贪心
1. 当优化答案对当前状态没有改变的时候，可以采取贪心。
2. 贪心可以无条件优化答案（CF520B Two Buttons）
双指针（CF279B Books）
限制条件的最长/最短连续子序列和。
ll p=1,len=0,maxlen=0,sum=0;
for(ll i=1; i<=n; ++i) {
sum+=arr[i];
++len;
while(sum>m) {
sum-=arr[p];
--len;
++p;
}
maxlen=max(len,maxlen);
}关于位运算
1. 异或运算相当于把1对应的被异或数位取反，0对应的被异或数位取反，例：
0010 1101^0000 1111=0010 0010
2. 异或的逆运算性质
1. n^m=k -> n^k=m（#735 (Div. 2) C Mikasa）
2. 判断序列中是否存在不成对的数：异或和=0，全部成对；异或和>0，存在不成对的数。
原理：a^a=0，a^b≠0 (a≠b)
3. 加法的位运算性质
1. 加法在某一位上的变化为异或运算，在进位上的运算为后一位的与运算
2. 加法运算时，低位一旦出现0，高位不会发生变化，低位不出现0，高位会出现1
组合博弈
1. 从至少一个N点能到达P点
2. 从P点只能到达N点
SG函数
SG值为不等于后继SG值的最小非负整数。
SG（x）=0 P点
SG（x）>0 N点
Nim-sum（小博弈的并）
对于nim游戏的某个位置（x1，x2，x3，...），当且仅当sg(x1)⊕sg(x2)⊕sg(x3)⊕...=0时（x1，x2，x3）为P点。
操作为，找到异或和最高位，三个对应位有几个1就有几种取法（保证取牌数为正）。
证：
终结位置（0,0,0）为P点。
任何P点只能到N点，任何不等于0的异或和都为N。
至少有一个N能到达P，不等于0的异或和，取xn改变其中几个位数使得异或和为0。
图论
几个建图方式：
1. 点、边方式
2. 出入度方式
拓扑排序：
1. 拓扑排序可以反向建图，拓扑顺序相反，不改变先决条件关系
快速傅里叶变换（FFT）
自学：多项式、多项式点值表示法、点值表示法多项式乘积、复数乘法、单位根、单位根的幂和性质
投递美团等公司10个岗位
