这题其实就是点分治的一个扩展。

水！ 离散化之后树状数组随便乱搞就行了。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758#include <bits/stdc++.h>#define MAXN 1000005using namespace std...

BZOJ GDOI 一句话题意：给你l,rl,rl,r，求a[l],a[l+1]...a[r]a[l],a[l+1]...a[r]a[l],a[l+1]...a[r]逆序对个数。 按照套路，我们先离散化。 然后考虑加入一个数会对逆序对做出多少贡献，先考虑我们从左边加入一个数，如图： 显然，只有严格小于他的数才会对答案产生贡献。 再考虑在右边加入一个数，如图： 显然，只有严格大于他的数才会...

洛古 GDOI 首先，看见“权值∈[a,b]\in [a,b]∈[a,b]的权值的种类数。”这样的话就要想到莫队。 我们有一个比较显然的树状数组做法，每次加进一个数，如果没有出现，那么加进树状数组，删除也是类似，最后前缀和相减统计一下即可。 1234567891011121314151617181920212223242526272829303132333435363738394041424...

首先，以aaa为第一关键字排序，bbb为第二关键字排序，ccc为第三关键字排序，这样从左到右扫过去，发现aia_iai​一定是递增的，所以只要考虑后面两维即可。 不妨考虑画一个图： 发现只有在蓝色框框里面的才是合法的解（如(bj,cj)(b_j,c_j)(bj​,cj​)，(bk,ck)(b_k,c_k)(bk​,ck​)） 。 Sol1 我们用树套树（线段树套动态开点线段树，又称二维线...