本文主要是介绍Codeforces 538F A Heap of Heaps 离线+树状数组+离散化，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
给你n个数，这n个数构成1,2……,n-1叉树。
问你构成1~n-1叉树，儿子比父亲大（即不符合最小堆的情况）的个数分别是多少。
思路：
首先把每个询问区间都求出来（每个询问区间分为两个区间，询问[l,r]，则分为[1,l-1]和[1,r]）两个for循环，遇到不存在的区间直接break。复杂度不会超，证明不会证= =||
然后根据右端点从小到大排序（左端点都是1，因此结构体中不记录）。
最后边查询边更新树状数组。
查询更新操作：
如果我们要查询一个区间[l,r]，比x小的个数。则只需要查询[1,l-1]比x小的个数，再求出[1,r]比x小的个数，相减后就是所要结果。
因此最后的查询操作本质思想就是上面提到的；
更新：根据数值离散化后的大小插入。
*区间数组大小开到1e7才过，好凶。。。
*cf中看别人代码，还有一种更好的方法来求，代码量，时间空间复杂度都要小。也是离散+树状数组做的，但没看懂。。悲剧。。
结构体解析：
idx：右端点（用于排序）
x：数值离散化后的值（用于询问的区间）
k：第k叉树
flag：0/1：减去查询所得的值/加上查询所得的值。
struct Seg {int idx, x;int k, flag;bool operator < (const Seg &t) const {return idx < t.idx;} }seg[(int)1e7];
code：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;const int N = 2*1e5+5;
typedef long long LL;int n;
int a[N], b[N];
int res[N];
int bit[N];
struct Dz {int a[N], n;void push(int val) {a[n++] = val;}void ok() {sort(a, a+n);n = unique(a, a+n)-a;}int find(int val) {return lower_bound(a, a+n, val)-a;}
}lsh;int cnt = 0;
struct Seg {int idx, x;int k, flag;bool operator < (const Seg &t) const {return idx < t.idx;}
}seg[(int)1e7];inline int lowbit(int t) {return t&(-t);
}void update(int idx) {while(idx <= n) {bit[idx]++;idx += lowbit(idx);}
}int query(int idx) {int ret = 0;while(idx > 0) {ret += bit[idx];idx -= lowbit(idx);}return ret;
}void solve() {//get segmentfor(int i = 1;i <= n; i++) {for(int j = 1;j <= n-1; j++) {int l = j*(i-1)+2, r = min(n, j*i+1);if(l > n) break;seg[cnt++] = {l-1, b[i], j, 0};seg[cnt++] = {r, b[i], j, 1};}}sort(seg, seg+cnt);int cur = 1;for(int i = 0;i < cnt; i++) {Seg &e = seg[i];while(cur <= e.idx) {update(b[cur]);cur++;}int &t = res[e.k];int tmp = query(e.x-1);if(e.flag == 1)t += tmp;else t -= tmp;}for(int i = 1;i <= n-1; i++)printf("%d%c", res[i], i == n-1 ? '\n':' ');
}int main() {scanf("%d", &n);lsh.n = 0;for(int i = 1;i <= n; i++) {scanf("%d", &a[i]);lsh.push(a[i]);}lsh.ok();for(int i = 1;i <= n; i++) {b[i] = lsh.find(a[i])+1;}solve();return 0;
}
这篇关于Codeforces 538F A Heap of Heaps 离线+树状数组+离散化的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
