Mutual Training for Wannafly Union #6

=w=

QvQ

题意：有长度为n的序列(n<=5e5)，求满足条件的a,b,c,d的组数，要求满足条件：min([a,b])<=min([c,d])，a<=b<c<=d

分析：数据结构(set+BIT)

　　　不妨把所有点按照从小到大的顺序加入数组

　　　那么当一个数x进入数组时候，已经在数组里的数一定小于等于它

　　　我们考虑以x为min([a,b])的方案数

　　　很明显我们可以找到该位置的l和r（set）

　　　那么a只能在l~x之间，b只能在x~r之间，而c,d只能在空隙之中

　　　用乘法原理计数，关键问题就是计算r后面的所有空隙对答案的贡献

　　　这个贡献可以用树状数组来维护

　　　c[i]表示i位置的板子到前驱板子之间的空隙对答案的贡献，那么对于每次询问，计算r后面的所有空隙对答案的贡献就是query(n+1)-query(r)

　　　对于每个修改，x插入到l和r之间，c[l]值不需要改变，c[x]值加上l~x长度的贡献，c[r]需要减去原来l~r长度的贡献，再加上x~r长度的贡献

题意：T组数据，n*m的格子(T,n,m<=1000)，将1~n*m填入这些格子中，规定位置(i,j)的高度为(i xor j)，要求若位置A的高度严格大于位置B，那么A中的数字也必须严格大于B中的数字，求放置方案数

分析：各种方法

　　　对于极限情况，异或值最大为1023

　　　如果我们按照i xor j对所有位置排序，那么异或值相同的位置必定只能取1~n*m中连续的一段，所以如果p[x]表示异或值为x的位置有多少个，那么答案就是π(p[x]!) (0<=x<=1023)

　　　方法一：暴力

　　　　　有了上面的结论，很直观的想法就是对于每组数据，直接n*m统计xor值，时间复杂度O(TNM)，是1e9级别的，但是因为运算是异或，所以跑得过，而且跑得十分快……

　　　方法二：离线+二维树状数组

　　　　　将询问离线，枚举每个异或值x，计算各个询问中该异或值出现了多少个

　　　　　这相当于提前预处理得到每个异或值x的出现位置有哪些，用vector记下来

　　　　　然后对于每个枚举的x，把那些位置在二维数组中标1，其他标0,

　　　　　对于每个询问T的n和m，也就是询问[1,n][1,m]数组的和，这当然可以用二维树状数组完成

　　　　　O(T*1023*logn*logm)，最坏是1e8级别的，实际和暴力时间差不多

　　　方法三：数位dp

　　　　　dp[i][j][k][l]表示前i位，第一个数字是否有限制，第二个数字是否有限制，当前异或值为l的方案数

　　　　　O(T*10*2*2*1023*2*2），大概是1e8级别的，实际跑很慢，比暴力慢

　　　方法四：FWT

　　　　　设s[x]表示异或值x出现的个数

　　　　　那么计算方法是s[x]=Σf[i]*g[j] (i xor j==x)，此题中f[i]=i,g[j]=j

　　　　　这种卷积不再是i+j==x，而是i xor j==x，可以用FWT优化到nlogn的

　　　　　那么复杂度就是O(Tnlogn)是1e7级别的，实际跑得是最快的

　　　　　另外，FWT还可以处理OR、AND、~AND、~OR、~XOR

WVW

待填坑

巴特西