A#G/C013

2024-03-02 18:17:28

A Sorted Arrays

不会/kk

我是傻逼

如果一条路径不合法，那么把不合法的端点向没出现过的相邻点连过去救星了

我是傻逼

显然最后的位置可以直接求出，环上相对位置不变。

然后要确定一个位置的答案

假设每个蚂蚁手上有一只鸡，鸡的数字递增相遇就交换手上的鸡，不改变方向

那么蚂蚁1如果向右走，由于相对位置不变每交换一次鸡的数字会增加1

交换鸡的次数就是蚂蚁1碰到其他蚂蚁的次数，可以直接算出来

每次操作球的变化量最多是1，可以dp记录每次的黑球量，然而有重复，多加一维记第二维是否触底就行了

首先可以容斥，\(F_i=f(x_i)-\sum_{j<i}f(x_i-x_j)F_j\)

\(f(x)\)就是长度为\(x\)的区间分正方形的权值和

~~打表发现是http://oeis.org/A033453然后可以矩乘优化转移~~

\(f\)递推式是\(f_i=\sum_{j<i}(i-j)^2f_j\)

考虑平方的意义就是区间内放两个球的方案数所以可以\(f[0/1/2]\)表示放了几个球，也可以矩乘优化

神仙题

首先离散化\(C\)，按照\(C\)离散化\(A,B\)，现在\(C=[1-(n+1)]\)，\(A,B\)离散化了意义不变

搞一个\(c\)数组，初始是\(c_i=-1\)，然后默认所有牌选正面，就是让\(c_{A_i}++\)

还要加上来一张牌，如果那张牌选上来的数字是\(x\)，再把一个\(c_x++\)，要求能配对的条件是所有前缀和\(\ge 0\)

那么不考虑新的那张牌，前缀和应该是\(1-(x-1)\)这段\(\ge 0\)，\(x-n\)这段\(\ge -1\)

然而你全选正面很可能不合法，这个时候就要把一些正面换成反面

首先让所有前缀和\(\ge -1\)，从右往左腾讯（我也不知道为啥从左往右捕星）如果\(S_i<-1\)就选一个左端点最小的区间\([B_i,A_i)\)加上\(1\)

再从左往右如果\(S_i<0\)就选右端点最大的区间，可以得出每个\(ans_i\)，表示\(1-(i-1)\)这段\(\ge 0\)，\(i-n\)这段\(\ge -1\)最多用多少正面