ComplexPug

分类

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

/ 注册

全部文章（共13篇）

P3901 数列找不同

P3901 数列找不同题目描述现有数列 \(A_1,A_2,\cdots,A_N\) ，Q 个询问 \((L_i,R_i)\) ， \(A_{Li} ,A_{Li+1},\cdots,A_{Ri}\) 是否互不相同输入输出格式输入格式：第1 行，2 个整数 \(N,...

莫队

2018-07-18

0 531

P2709 小B的询问

题目描述小B有一个序列，包含N个1~K之间的整数。他一共有M个询问，每个询问给定一个区间[L..R]，求Sigma(c(i)^2)的值,其中i的值从1到K，其中c(i)表示数字i在[L..R]中的重复次数。小B请你帮助他回答询问。输入格式：第一行，三个整数N、M、K。...

莫队

2018-07-18

1 456

HDU 4638Group （莫队）

Group Problem Description There are n men ,every man has an ID(1..n).their ID is unique. Whose ID is i and i-1 are friends, Whose ID is i and i+1 ar...

莫队

2018-07-20

1 432

BZOJ 3339 && luogu4137 Rmq Problem / mex(莫队)

P4137 Rmq Problem / mex 题目描述有一个长度为n的数组{a1,a2,…,an}。m次询问，每次询问一个区间内最小没有出现过的自然数。输入输出格式输入格式：第一行n,m。第二行为n个数。从第三行开始，每行一个询问l,r。输出格式：一行一个数，表示每个...

莫队

2018-07-21

1 649

P4113 [HEOI2012]采花 (莫队TLE)

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

莫队树状数组

2018-07-21

1 531

P3709 大爷的字符串题

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

离散化莫队

2018-10-18

0 452

CF375D Tree and Queries

题目 luogu 思路唯有水题暖人心只用子树的树，当然dfs序列区间查询出现k次的数字的个数 nub[i]记录出现次数大于i的数字个数发现只是O(1)的转移，想想就OK了代码 ps:为了更好地阅读，我加一段cpp吧 void add(int x) { hav[x]...

dfs序莫队

2018-10-18

0 500

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

P1903 [国家集训队]数颜色 / 维护队列

关于时间复杂度对于多维莫队的复杂度差不多为\(O(n^{\frac{2k-1}{k}})\) 摘自zhihu大佬奇偶分类优化 return a.l == b.l ? (a.l & 1) ? a.r<b.r: a.r>b.r : a.l < b.l; 貌似不会...

莫队

2018-11-02

0 443