传送门 此题思路还是非常巧妙的。 考虑我们莫队的 Add 函数，本质上是往原本的区间里面加上一个数，然后算这个数的贡献。 比如说我们设 f(x,[l,r])f(x,[l,r])f(x,[l,r]) 为 ∑i=lr[cnt(x⊕a[i])=k]\sum _{i=l}^r [cnt(x \oplus a[i])=k]∑i=lr​[cnt(x⊕a[i])=k]（中括号里面为真时，值为 1，cntc...

传送门 为了方便，定义a[i]=g[i]a[i]=g[i]a[i]=g[i]。 首先做一次差分，将∑y=lrdist(y,x)\sum _{y=l} ^r dist(y,x)∑y=lr​dist(y,x)变成∑y=lxdist(y,x)−∑y=r+1xdist(y,x)\sum _{y=l}^x dist(y,x) - \sum _{y=r+1}^x dist(y,x)∑y=lx​dist(...

传送门 首先，附送本题数据生成器： 1234567891011121314151617181920#include <bits/stdc++.h>using namespace std;inline int gen(){ return (rand()<<15)|(rand());}int main(){ srand(time(...

传送门 洛谷上面翻译有毒，一是没有数据范围，其实n≤200000n \le 200000n≤200000，二是没有样例，这里粘贴一组SPOJ\rm SPOJSPOJ样例，和自己的对拍数据。 SPOJ\rm SPOJSPOJ样例 12345678910111213141516input:41 2 3 57Q 0 2 0I 3 4Q 2 4 1D 0Q 0 3 1R 1 2Q 0 1 0outp...

传送门 毒瘤lxllxllxl数据结构题。 首先，考虑传统的STSTST表，发现n=2000000n=2000000n=2000000，空间开不下。 考虑分块+ST+ST+ST表，每个块里面存的是块内前缀最大值，后缀最大值。 最后STSTST表查询的是块的最大值。 注意查询的区间[l,r][l,r][l,r]在同一块内需要暴力搞一下，发现数据随机，所以出现这种情况不多。 为了卡常数，需要预处...

传送门 题面大意： 长度为nnn的数列，支持两种操作： 1.1.1.修改某个位置的值 2.2.2.询问区间[l,r][l,r][l,r]里选出至多kkk个不相交的子段和的最大值。 一共有mmm个操作 解法： 暴力 dpdpdp+滚动数组（在本地卡进2s2s2s） 模拟赛的时候有人用这个方法AAA了 dp[i][j][p]dp[i][j][p]dp[i][j][p]表示进行到a[i]a[...

传送门 树套树模板题（线段树套FHQTreap\rm FHQ TreapFHQTreap） 一开始听说FHQTreap\rm FHQ TreapFHQTreap常数大，会TLE\rm TLETLE，就没敢写，最后发现FHQTreap\rm FHQ TreapFHQTreap还是能过的。 好了步入正题： 考虑在线段树的每个节点开一棵FHQTreap\rm FHQ TreapFHQTreap，...