蓝桥杯-2014-B组-10-小朋友排队（拓展树状数组模板）蓝桥杯-2014-B组-10-小朋友排队（

【蓝桥杯-2014-B组-10-小朋友排队（拓展树状数组模板）】使用到了普通的树状数组和拓展的树状数组。
普通的只能单点修改和区间查询，利用两次区间查询可以做到单点查询。如果要区间修改时间复杂度是O(n)。
拓展树状数组可以区间修改和区间查询，利用两次区间操作即可实现单点操作，但增加了一个额外的数组。
题目思路是用一个普通bit记录该点是否未排序。一个拓展bit记录被排序次数。

然后模拟插入排序，选取最小点，该点左边的点被排序次数都+1（已排序的点可能会被再次累加，但不影响，原因见第4步）。
该点的被排序次数+n，n显然等于该点左边未排序的点的数量。
接着更新该点的未排序标志。
接着该点将不会参与后续排序，所以可以直接累加该点；由于后续不会再使用该点的被累加次数，所以再次执行第1步时，错误累加该点的被排序次数不会对结果造成影响。

#pragma warning(disable:4996) #include #include #include #include using namespace std; typedef unsigned long long ull; int isDebug = 0; pair childs[20]; // hight, index int unhappy[20 + 1]; // 拓展bit 记录被排序次数 int unhappy2[20 + 1]; int counts[20 + 1]; // 普通bit 记录该点是否未排序// 普通bit 单点修改 bit[i] += x void bitAdd(int* bit, int i, int x) { while (i < 21) { bit[i] += x; i += i & -i; } }// 拓展bit 区间修改 bit[i, N] += x void bitAdd(int* bit1, int* bit2, int i, int x) { int ii = i; while (i < 21) { bit1[i] += x; bit2[i] += x * (ii - 1); i += i & -i; } }// 普通bit 区间查询前i项和 int bitSum(int* bit, int i) { int s = 0; while (i > 0) { s += bit[i]; i -= i & -i; } return s; }// 拓展bit 区间查询前i项和 int bitSum(int* bit1, int* bit2, int i) { int s = 0; int ii = i; while (i > 0) { s += ii * bit1[i] - bit2[i]; i -= i & -i; }return s; }// 遍历单点查询 void debug() { if (!isDebug) return; int i, last = 0, now = 0; for (i = 1; i < 6; i++) { now = bitSum(unhappy, unhappy2, i); printf("%d\n", now - last); last = now; } printf("\n"); }int main(void) { freopen("q.txt", "r", stdin); int n, N, h, index; int last = 0, now = 0, ans = 0; scanf("%d", &N); for (n = 0; n < N; n++) { scanf("%d", &h); childs[n].first = h; childs[n].second = n + 1; }sort(childs, childs+n); for (n = 1; n < 21; n++) bitAdd(counts, n, 1); debug(); for (n = 1; n < 21; n++) bitAdd(unhappy, unhappy2, n, 0); debug(); for (n = 0; n < N; n++) { index = childs[n].second; // 1 o[1, index - 1] += 1 bitAdd(unhappy, unhappy2, 1, 1); debug(); bitAdd(unhappy, unhappy2, index, -1); debug(); // 2 o[index] += index - n - 1 int leftCount = bitSum(counts, index-1); bitAdd(unhappy, unhappy2, index, leftCount); debug(); bitAdd(unhappy, unhappy2, index + 1, -leftCount); debug(); // 3 计数数组中删除该节点 bitAdd(counts, index, -1); // printf("%d %d\n", index, bitSum(unhappy, unhappy2, index) - bitSum(unhappy, unhappy2, index - 1)); // 4 index = bitSum(unhappy, unhappy2, index) - bitSum(unhappy, unhappy2, index - 1); ans += (1 + index) * index / 2; }printf("%d\n", ans); return 0; }