DDOSvoid's Blog

简介

给出一个某种元素的序列 $a_1,a_2,\cdots, a_n$，要求进行 $m$ 次询问，每次询问是一段区间 $[l,r]$ 的某种支持结合律和快速合并的信息，要求在线

题目描述

https://loj.ac/p/6682

简要题意：给定 $n$​，求 $\frac{1}{2}\sum_{i=1}^n\sigma_0^2(i)-\sigma_0(i)$​

$n\le 10^{10}$​

题目描述

https://loj.ac/p/6235

简要题意：求 $1\sim n$ 的素数个数

$n\le 10^{11}$

题目描述

https://www.luogu.com.cn/problem/P5325

简要题意：定义积性函数 $f(x)$，且 $f(p^x)=(p^x)^2-p^x$，求 $\sum_{i=1}^nf(i)$

$n\le 10^{10}$

题目描述

http://codeforces.com/problemset/problem/710/F

简要题意：有三种操作，操作一向集合中加入一个字符串，操作二从集合中删除一个字符串，操作三给定一个模板串，查询集合中的串在模板串中出现次数的总和

$len\le 3\times 10^5$

简介

大概是某种意义上线段树分治和 $cdq$ 分治的替代品

题目描述

https://www.luogu.com.cn/problem/P4655

简要题意：有 $n$ 根柱子，每根柱子高度为 $h_i$，如果要架桥在 $i$ 和 $j$ 两根柱子间，需要花费 $(h_i-h_j)^2$，同时会拆掉 $i$ 到 $j$ 之间所有其它柱子，拆掉第 $i$ 根柱子的代价是 $w_i$，求连通 $1$ 和 $n$ 的最小代价，需要注意任意两座桥不能相交除了端点之外的地方相交

$n\le 10^5,0\le h_i,|w_i|\le 10^6$

题目描述

https://www.luogu.com.cn/problem/P3195

简要题意：给定一个长度为 $n$ 的序列 $a$ 和 $L$，现在需要将序列分成若干段，如果将 $a_i$ 到 $a_j$ 放到一段，那么它们的代价是 $(j-i+\sum_{k=i}^ja_k-L)^2$，求最小代价

$n\le 5\times 10^4$

题目描述

https://acm.hdu.edu.cn/showproblem.php?pid=6987

简要题解：给定 $n$，求所有长度为 $n$ 的 $01$ 串的价值总和，一个 $01$ 串的价值定义为 $\lfloor\frac{n}{k}\rfloor$，其中 $k$ 是这个 $01$​ 串的最小周期

$n\le 10^9$

题目描述

https://acm.hdu.edu.cn/showproblem.php?pid=6989

简要题意：给定一个长度为 $n$​ 的序列 $a$​，有 $m$​ 次询问，每次给定询问区间 $[l,r]$​，求 $\sum_{l\le x\le y\le r} \frac{\frac{max~a_{x\cdots y}+min~a_{l\cdots r}}{2}}{\frac{n(n+1)}{2}}$，可以离线​

$n,m\le 3\times 10^5$