ComplexPug

分类

做题记录(1) 未归档(274)

/ 注册

全部文章（共10篇）

加强树状数组luogu3368

暴力树状数组30分，这该怎么办；知识点回顾差分数组中开头结尾改变了值之后求他的前缀，发现区间内所有数都改变然后我们做差分树状数组 #include<cstdio> using namespace std; int n,m; int c[501010...

树状数组

2018-05-03

0 427

P4113 [HEOI2012]采花 (莫队TLE)

思路 update 11.2 树状数组ＡＣ本题莫队过不去，会TLE ----------------------- 但也是个不错的莫队练手题 ------------------------ 毕竟Chen_Zhe还给了100分莫队分（还会给你小对勾） ---------------------...

莫队树状数组

2018-07-21

1 531

loj 诗歌

链接链接思路好久之前的考试题了吧，之前貌似抄的题解现在理解了怕忘了,就写个题解记录一下吧，题目还是不错的枚举中间点j \[H_{i}-H_{j}=H_{j}-H_{k}\] \[H_{k}+H_{i}=2*H_{j}\] 由于H是一种n的排列，所以取值就是\([1,n]\) 那就可以...

树状数组

2018-10-14

1 489

P4396 [AHOI2013]作业

题目链接 luogu4396 思路唯有水题暖人心咕了4天，今天跟着std对拍才做出来不得不说题解真的水的一批先离散化一下第一问差分询问，权值树状数组套一套就好了 \(nlog_{n}\) 第二问，Emma 莫队，加上树状数组维护修改 \(nlog_{n}sqrt_{n}\) \(3s\...

莫队树状数组暴力离散化

2018-10-22

0 414

P4303 [AHOI2006]基因匹配未完成

题目 luogu 暴力60pts部分显然如果没有出现次数==5的条件显然是\(N_{2}\)的求lcs的模板但是加点条件就完全不同了思路这个题短小精悍，不想数据结构那么***无脑我们考虑一下\(N_{2}\)的缺点首先我们知道，只有a[i]==b[j]的时候才会对答案有所贡...

DP 树状数组

2018-10-31

0 527

P3128 [USACO15DEC]最大流Max Flow

思路这个题哪里有那么费脑筋我们可以树链剖分嘛LCT昨天学的时候睡着了，不是太会两遍dfs+一个5行的BIT 其实树链剖分学好了对倍增和LCT理解上都有好处一条路径上的修改由于一条剖出来的链是连续的，我们要选择数据结构维护不过这里不用维护太多东西，只是区间+1 我们可以选择常数小，好写的...

树状数组树链剖分

2018-12-26

0 508

bzoj3262: 陌上花开树套树

链接 https://www.lydsy.com/JudgeOnline/problem.php?id=3262 思路 CDQ版本稍后再说二维偏序排序用树状数组求就可以而三维之后就不可以了，但我们可以在BIT上维护一个功能强大的treap 维护多出来的一维c BIT套treap a...

树状数组 fhqtreap 树套树

2019-02-10

0 498

bzoj [SDOI2014]数表莫比乌斯反演 BIT

bzoj [SDOI2014]数表莫比乌斯反演 BIT 链接 bzoj luogu loj 思路 \[ \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}a*[f[gcd(i,j)]<=a] \] \[ f[]可以O(n)预处理出来 \] \[ ...

莫比乌斯函数莫比乌斯反演树状数组线性筛

2019-05-04

0 611

bzoj1935: [Shoi2007]Tree 园丁的烦恼lowbit 离散化

链接 bzoj 最好不要去luogu，数据太水思路一个询问转化成四个矩阵，求起点\((0,0)到(x,y)\)的矩阵离线处理，离散化掉y，x不用离散。一行一行的求，每次处理完一行之后下一行的贡献直接叠加到当前。用lowbit统计错误离散化小心点，是y-1不是y 代码 #i...

树状数组离散化

2019-06-05

0 566

bzoj 2716: [Violet 3]天使玩偶

bzoj 2716: [Violet 3]天使玩偶链接 bzoj 思路 80s的评测交了五六发、、、貌似卡评测了只讨论在左下角的点，cdq分支求出。然后剩下的用坐标对称啥的再来三遍。不过每次还原这样是会T的。对x排序，然后搞就过了，（我也不知道，不过还是40s左右） KD-tree...

cdq 树状数组

2019-06-06

0 476