L - A Heap of Heaps
这个是一个还比较裸的静态主席树。
这个题目的意思是把这个数组变成k叉树，然后问构成的树的子树小于等于它的父节点的对数有多少。
因为这个k是从1~n-1 所以直接暴力肯定是不对的，所以可以用主席树来查询区间第k大。
查询的次数大约为n+n/2+n/3+...n/n 差不多是n*log(n) 的复杂度，建个主席树，直接查询即可
#include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <queue> #include <vector> #define inf 0x3f3f3f3f #define inf64 0x3f3f3f3f3f3f3f3f using namespace std; const int maxn = 2e5 + 10; int n, m, root[maxn], a[maxn], b[maxn], cnt; int sum[maxn << 5], lc[maxn << 5], rc[maxn << 5]; void build(int &rt, int l, int r) { rt = ++cnt; sum[rt] = 0; if (l == r) return; int mid = (l + r) >> 1; build(lc[rt], l, mid); build(rc[rt], mid + 1, r); // printf("rt=%d l=%d r=%d ",rt,l,r); } int update(int rt, int l, int r, int pos) { // printf("ww rt=%d l=%d r=%d pos=%d ", rt, l, r, pos); int id = ++cnt; sum[id] = sum[rt] + 1; // printf("rt=%d sum[%d]=%d ", rt, id, sum[id]); lc[id] = lc[rt], rc[id] = rc[rt]; if (l == r) return id; int mid = (l + r) >> 1; // printf("mid=%d rt=%d l=%d r=%d pos=%d ", mid,rt,l,r,pos); if (pos <= mid) lc[id] = update(lc[id], l, mid, pos); else rc[id] = update(rc[id], mid + 1, r, pos); // printf("rt=%d l=%d r=%d pos=%d ", rt, l, r, pos); return id; } int query(int l, int r, int u, int v, int h) { int mid = (l + r) >> 1; int x = sum[lc[v]] - sum[lc[u]]; //printf("l=%d r=%d u=%d v=%d h=%d mid=%d x=%d %d ", l, r, u, v, h, mid, x, sum[v] - sum[u]); if (l == r) return sum[v] - sum[u]; //printf("ww l=%d r=%d u=%d v=%d h=%d mid=%d x=%d ", l, r, u, v, h, mid, x); int ans = 0; if (h <= mid) ans = query(l, mid, lc[u], lc[v], h); else ans = x + query(mid + 1, r, rc[u], rc[v], h); return ans; } int main() { cnt = 0; scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &a[i]), b[i] = a[i]; sort(b + 1, b + 1 + n); int len = unique(b + 1, b + 1 + n) - b - 1; //printf("len=%d ", len); build(root[0], 1, len); for (int i = 1; i <= n; i++) { a[i] = lower_bound(b + 1, b + 1 + len, a[i]) - b; // printf("a[%d]=%d ", i, a[i]); root[i] = update(root[i - 1], 1, len, a[i]); } // if(len==1) // { // for (int i = 1; i < n; i++) printf("0 "); // printf(" "); // return 0; // } for (int i = 1; i <= n - 1; i++) { int j = 1, ans = 0; while (i*j + 1 <= n) { int l = i * (j - 1) + 1, r = i * j + 1; if (a[j] - 1 != 0) ans += query(1, len, root[l], root[r], a[j] - 1); j++; } if (i*j + 1 > n&&i*(j - 1) + 2 <= n) { int l = i * (j - 1) + 1, r = n; if (a[j] - 1 != 0) ans += query(1, len, root[l], root[r], a[j] - 1); } printf("%d ", ans); } printf(" "); return 0; }