题意给出一个长度为 $n(\le 2\times 10^6)$ 的数列，有 $m(\le 2\times 10^6)$ 次询问，求 $[l,r]$ 之间有多少个出现了两次及以上的数。题解和 HH的项链 差不多，只是要求出现两次。所以把树状数组维护的值修改一下，变成只有出现了两次才更新节点的权值。先预处理出每种数字下一次和下下次出现的位置 $nxt[]$ 和 $nxt2[]$，并把所有数字出现...
当时比赛的时候没做出来这题，做了 洛谷3586 才知道这题的做法。题意有 $N(\le 3\times 10^5)$ 张卡，卡上有数字 $A_i(\le n)$ 。$\forall k$ ，问：每次取 $k$ 张数字互不相同的卡，能取多少次。题解记录每个数字出现的次数为 $s_i$ ，问题就转化为：每次选 $k$ 个正数 $-1$ ，最多操作多少次。然后就可以直接用 洛谷3586 的结论了（...
题意给出一个长度为 $n(\le 10^6)$ 的全 $0$ 序列，要求支持以下操作：单点修改给出 $(c,s)$ ，每次取 $c$ 个正数 $-1$ ，问能否操作 $s$ 次。题解先考虑操作 $2$ 。设 $\geq s$ 的数有 $x$ 个，这些数每次都可以取，此外还需要 $(c-x)$ 个数。设 $< s$ 的数的和为 $sum$ ，如果 $sum < (c-s)\time...
题意有两个序列 $a,b$ ，可以把 $b$ 中相邻的数交换，使得 $\sum (a_i-b_i)^2$ 最小。问最少要交换几次？题解可以发现最小的情况就是 $a,b$ 中数字的大小顺序相同，所以离散化后建立 $a$ 中大小在 $b$ 的对应关系 $s$ ，求 $s$ 的逆序对个数即可。#include<bits/stdc++.h>
#define ha 99999997
us...
题意有 $N$ 个数，可以进行 $K$ 次操作，每次可以选择一个区间，把其中所有数 $+1$ 。求最后最长不降子序列的长度。$N\le 10000 \ , \ K\le 500$ 。题解可以发现，每次选择区间的右端点一定是 $N$ ，否则就可能出现答案减小的情况，而不可能会增加。用 $f[i][j]$ 表示第 $i$ 个数被操作了 $j$ 次 ，前 $i$ 个数的最优情况。可以得到方程：$$...
题意给出 $n$ 个数，求逆序对个数。其中 $n\le 500000$ ，每个数 $\le 999,999,999$ 。题解数的范围很大，所以直接用树状数组肯定不行。但事实上我们只关心数之间的顺序，所以排序后用 $\text{ord[]}$ 记录顺序即可。#include<bits/stdc++.h>
#define ll long long
using namespace s...