Day 8

（Nerlci_终于回来更不知道咕咕了多少天的随笔了qwq）
在经历了CCPC2019网络选拔赛和两场百度之星初赛的洗礼之后，今天机房的题目回到了“NOIP模拟赛”上（注意引号）（别问我要前面三场比赛的随笔，我只能说我会写的【趴）。不过大概是变成了先扫一眼题目->发现全不会做->安逸睡觉qwq

T1 树状数组

（鬼知道我怎么就把时间全用来肝这道题了）
说白了就是两个数l,r，跑x-=lowbit(x)，看跑出来有几个不相同的。其中1\le l \le r \le n。
事实上，我们可以发现，最后的结果就是l和r所有1的个数加起来再减掉它们在二进制下最长公共前缀的1的个数。我们可以先考虑一个时间复杂度需要O(n log n)的算法。我们知道，当n-1增大为n时，我们多出来的可取的l,r是(l,r)=(1,n),(2,n),\cdots,(n,n)。我们考虑这些数值对对答案的贡献。
对于l<2^{\lfloor \log_2n\rfloor}，显然在第\lfloor \log_2n \rfloor这一位上l为0，那么它和n最长公共前缀为0，我们直接考虑有多少个1即可。所有二进制下最多有k位的数包含的1加起来即为\sum\limits_{i=1}^{k}\ C_{k}^{i}*k个。由于0 \le k \le 63，所以实际上这个组合数算起来相当快，而且由于个数很少，你甚至可以像我一样打个表。那么对于每个l，n中1的个数就要被加进答案一次。设n中含1的个数为ctr(n)，令k=\lfloor log_2n \rfloor，那么在这一部分，答案即为\sum\limits_{i=1}^{k}\ C_{k}^{i}*k + 2^k-1*ctr(n)
对于l\ge2^{\lfloor \log_2n\rfloor}，我们知道它和n的公共部分最后是不需要统计的，而剩下的部分和上面的统计方法是一样的，那么我们直接从n的高位不断的拿走一个1再按上面重新统计一次即可，实现可以使用递归。注意到对于每个相同的n我们的统计的结果相同，我们可以加个记忆化上去。
由于上面算出来的东西只是n比n-1多出的部分，接下来我们需要花O(n)的时间递推出n时的答案，这里同样可以加一个记忆化（不加60\to30）。

是的你没有听错，这么长一大串的算法只能拿60！我们现在考虑正解。事实上我们完全可以直接枚举l,r的每一位来构造l,r并统计答案，只要保证1 \le l \le r \le n即可。这是一种二进制意义下的数位DP。
我们令f[i][0/1][0/1]中i表示当前枚举到从高位到低位数第i位，第一个0/1表示l和r前i位相同或不相同，第二个0/1表示r和n的前i位相同或不相同，f[i][0/1][0/1]表示满足以上条件的l，r，n的方案数，g[i][0/1][0/1]表示去除公共前缀中的1后所有方案加起来中1的个数。接下来枚举每一位并DP即可。
这个转移十分经典，这里不再赘述
我们考虑第i位每一种情况能从哪些情况转移而来。
对于n为1的位数，如下：

p[i + 1][1][1] = p[i][1][1]; //这一位只能填1
p[i + 1][0][1] = p[i][1][1] + p[i][0][1] * 2; //对于p[i][1][1],l填0，r填1
                                              //对于p[i][0][1],l填1或0，r填1
p[i + 1][1][0] = p[i][1][1] + p[i][1][0] * 2; //对于p[i][1][1],l填0，r填0
                                              //对于p[i][1][0],l,r填1或0
p[i + 1][0][0] = p[i][1][0] + p[i][0][1] * 2 + q[i][0][0] * 4; //对于p[i][1][0],l填0，r填1
                                                               //此处r不能填0的原因是l这一位与r必须不同，若r填0则l必须填1，这时l>r，不符合题意
                                                               //对于p[i][0][1]，l填1或0,r填0;
                                                               //对于p[i][0][0]，l填1或0,r填1或0

g[i][0/1][0/1]和当这一位为0时的转移类似，可以试试自己推导一下。
这样g[63][0][0]+g[63][0][1]+g[63][1][0]即是答案。

T2 雇佣妹抖

说白了就是给定k，求序列中所有大于k的数组成了多少个连续的段。
正解的思路十分巧妙。我们用两个树状数组，一个维护有多少数大于k，另一个维护选中的数有多少对是相邻的，这个可以用把相邻的两个数中最小的放入树状数组中维护。
查询的时候用大于k的数的个数减去相邻的对数即可得到答案。