ComplexPug

分类

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

/ 注册

全部文章（共7篇）

P3709 大爷的字符串题

题意询问区间众数出现的次数思路唯有水题快人心离散化+莫队莫队一定要先加后减，有事会出错的莫队维护区间众数: 维护两个数组，一个数组记录权值为x的出现次数，一个记录出现次数为x的数的个数 add很简单，更新ans delete的时候，删除的是ans话，查看出现次数为x的个数是否为1，...

离散化莫队

2018-10-18

0 452

P4396 [AHOI2013]作业

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

莫队树状数组暴力离散化

2018-10-22

0 414

bzoj3289 Mato的文件管理

题目 bzoj3289 思路区间求逆序对离散化+莫队+树状数组修改代码 /************************************************************** Problem: 3289 User: 3010651817 ...

莫队离散化暴力

2018-10-22

0 478

CF817F MEX Queries

题目 CF luogu 思路好菜呀数据太大，需要离散化但是离散化x的时候，需要带上x-1和x+1 因为这也有可能是答案，当然你分类讨论也阔以然后维护一下第一个1出现的位置和第一个0出现的位置代码 #include <iostream> #include <cst...

线段树离散化

2018-10-31

0 380

luogu P2617 Dynamic Rankings

前置知识: 普通主席树，树状数组大概待修主席树和静态的一样只不过还要加一颗树来维护你修改的值这棵树就是是树状数组,每个节点上再维护一颗动态开点线段树 (就是所说的树套树，不过没啥可怕的，就是麻烦一丢丢) 查询的时候老样子不过要多加上树状数组中的值罢了代码还算好些，如果主席树，...

线段树离散化数据结构-主席树树套树可持久化

2018-12-11

0 502

luogu P5105 不强制在线的动态快速排序

前言考试的时候居然想错了区间贡献，mdzz 思路题目看着很方啊，难道要树套树？但数据范围提醒我们，是nlogn的复杂度 Sort(S)的定义是不是很鬼畜但我们不动脑子的打表容易发现连续区间[1，n]内\(a_i^2-a_{i-1}^2\)为连续的奇数（其实这里直接用初中的完全平方公...

线段树离散化

2018-12-17

0 619

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

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

树状数组离散化

2019-06-05

0 566