博客
归档
友链
关于
博客
归档
友链
关于
P4887 【模板】莫队二次离线(第十四分块(前体))
传送门 此题思路还是非常巧妙的。 考虑我们莫队的 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...
2019-11-02
阅读全文
LOJ 6435.「PKUSC2018」星际穿越
传送门 为了方便,定义a[i]=g[i]a[i]=g[i]a[i]=g[i]。 首先做一次差分,将∑y=lrdist(y,x)\sum _{y=l} ^r dist(y,x)∑y=lrdist(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=lxdist(...
2019-09-14
阅读全文
P5071 [Ynoi2015]此时此刻的光辉
传送门 首先,附送本题数据生成器: 1234567891011121314151617181920#include <bits/stdc++.h>using namespace std;inline int gen(){ return (rand()<<15)|(rand());}int main(){ srand(time(...
2019-08-01
阅读全文
SP19543 GSS8 - Can you answer these queries VIII
传送门 洛谷上面翻译有毒,一是没有数据范围,其实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...
2019-07-27
阅读全文
P3793 由乃救爷爷
传送门 毒瘤lxllxllxl数据结构题。 首先,考虑传统的STSTST表,发现n=2000000n=2000000n=2000000,空间开不下。 考虑分块+ST+ST+ST表,每个块里面存的是块内前缀最大值,后缀最大值。 最后STSTST表查询的是块的最大值。 注意查询的区间[l,r][l,r][l,r]在同一块内需要暴力搞一下,发现数据随机,所以出现这种情况不多。 为了卡常数,需要预处...
2019-07-21
阅读全文
CF280D k-Maximum Subsequence Sum 线段树
传送门 题面大意: 长度为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[...
2019-07-13
阅读全文
P3380 【模板】二逼平衡树(树套树)
传送门 树套树模板题(线段树套FHQTreap\rm FHQ TreapFHQTreap) 一开始听说FHQTreap\rm FHQ TreapFHQTreap常数大,会TLE\rm TLETLE,就没敢写,最后发现FHQTreap\rm FHQ TreapFHQTreap还是能过的。 好了步入正题: 考虑在线段树的每个节点开一棵FHQTreap\rm FHQ TreapFHQTreap,...
2019-07-13
阅读全文