Codeforces 371
看到这次Div1是三个2000的(而不是2500)，另外看到叉姐在论坛上放出题解，莫名其妙自己也想做一做。。。
Div2A Meeting of Old Friends
题意是给出两个区间，求交集的区间的长度，如果k在这个交集里面，那么结果再减1。
Div2B Filya and Homework
题意是给出n个数，现在能在一些数上(可以是0)上加x，也可以在一些数上减x，问能否最终的值是相等的。
分析可知如果n个数的值只有小于三种的话，那么是一定可以的。如果是等于三种，要形成等差数列。如果是大于三种，那么没可能了。
DIV1A Sonya and Queries
题意是给出一种匹配方法，给出一个01串，将数字从右到左匹配。如果是0，要求该位置是偶数；如果是1，要求该位置是奇数。
每次有三种操作，1.向该集合添加一个数字。2.向该集合删去一个数字。3.给定一个01串，询问该集合中符合该匹配的数字有多少个。
因为这个01串最多是18位，开一个1<<18的数组，暴力记录就可以了。
DIV1B Searching Rectangles
交互题，题意是在n*n(2<=n<=2^16)的格子上有两个矩形，两个矩形不重合。现在叫你找这两个矩形的位置。
每次你可以询问一个矩形，它会回答你里面有多少个完全在里面的矩形(0<=res<=2)。
先二分在横轴上存在把两个矩形分开的x，不存在就找y。
然后分别在分开的矩形内部，二分找四个边。
这个题叉姐写的代码真的很👍。。。
DIV1C Sonya and Problem Wihtout a Legend
题意是给出一个长度为n的序列，可以对每个数加上或减去一个数，将其改造成递增序列，问最小代价。
他们都说这个题烂大街了，然而我没做过。。。POJ 3666，CF Round13 C
首先要求递增的话，那么A[i]-=i，将A[i]排好序假设为B[i]。
然后数据是3000的话，O(n^2)的DP也是可以过的，DP[i][j]表示前i个数里面变成单调递增，且最后一个数是B[j]的最小代价。说白了，就是暴力每个数作为一段区间的中位数，考虑其代价(后面的左偏树也是基于这个优化的)。因为如果这个序列单调递增，那么代价为0.单调递减，那么代价就是每个数-中位数的和。
所以能够得到转移方程为
$$
dp[i][j]=min(dp[i-1][k])+|A[i]-B[j]| (k\leq i)
$$
O(nlogn)的方法是用左偏树，有专门的论文，题目接触的也比较少，只知道这个是一个可并堆，可以很方便最大最小值，这个题目维护的是中位数。。。
对于递增的区间，把每一个数看成单独的堆，中位数就是自己。碰到递减的区间，合并这两个区间，维护其中位数。这里面的左偏树是一个最小堆，而不能是最大堆。拿第二个例子来说，如果维护的是最大堆的话，那么中位数到第二个时是4，因为你要处理的是比当前区间中位数小的区间，维护最大堆的话，那么中位数2这个信息就没了，被之前pop掉了。
DIV1D Animals and Puzzle
题意是给出一个n*m的格子，格子上非0即1，现在有q个询问，询问当前矩形里面的最大的都是1的正方形的边长。
首先dp来求当前位置作为正方形的右下角，其最大边长是多少。转移方程为
$$
dp[i][j]=min({dp[i-1][j],dp[i][j-1],dp[i-1][j-1]})+1
$$话说这个dp出来之后没过几天的Google APAC Test也出了这个dp，泪流满面
然后构建一个二维的st表，对于每一个询问，二分答案mid，满足x1+mid-1,y1+mid-1,x2,y2这个区间里面有大于等于mid的值，就OK。否则就没有该边长的正方形。
DIV1E Sonya Partymaker
题意(这个题意给的不好啊。。。不过这个dp倒是又有些神。。。也是见的少，啥都神。。。)给出1到m的环，有n个人坐在相应的位置上，每个人在事先选择好一个方向，顺时针还是逆时针，然后就开始走，每走一步，将所在位置的椅子扔掉，问最少多久之后扔完所有的椅子。
先把这个位置整理成1到n之间空隙最大的位置，然后就像叉姐说的，会发现1和2一定有往左跑的，(假设都向右跑，那么一定不是最优)枚举这个往左跑的，dp[i]表示第i个人能够覆盖的最远位置。
考虑各种情况：
第i个人向右跑，要求dp[i-1]大于等于A[i]-1。dp[i]=max(dp[i],A[i]+x)
第i个人向左跑，可能会是第i-1个人向右跑，为了覆盖该段区间，要求dp[i-1]>=A[i]-x-1,dp[i]=max(dp[i],A[i])
第i个人向左跑，可能会是第i-2向右跑，为了覆盖该段区间，要求dp[i-2]>=A[i]-x-1，dp[i]=max(dp[i],A[i-1]+x)
学习到了rotate函数，rotate(begin,middle,end)把该数组[begin,middle) 与区间[middle,end]内的元素做了交换