之前用树状数组做这道题，没发现有什么问题。用线段数组后，总是报 runtime Error。后来发现是数组开小了。
# include <iostream> # include <algorithm> # include <memory.h> # include <vector> using namespace std; const int maxn = 500010; struct Num { int val; int pos; bool operator <(const Num &a)const { return val < a.val; } }num[maxn]; int n; struct Segment { // 因为不需要修改 struct _nod{ long long nums; int l, r; } TreeNode[maxn << 2]; //bug 之前开到 [maxn <<1] 直接报 runtime error。 线段树结构占用内存是树状数组的 4 倍，而且查询数据还没有树状数组快！ void init() { memset(TreeNode, 0, sizeof(TreeNode)); } void build(int index, int l, int r) { int mid = (l+r) >> 1; TreeNode[index].l = l; TreeNode[index].r = r; if (l == r) return; build(index <<1, l, mid); build(index << 1|1, mid+1, r); } void add_node(int index, int pos, int l, int r) { int mid = (l+r) >> 1; if ( l == r) { TreeNode[index].nums = 1; return; } if (mid >= pos) { add_node(index <<1, pos, l, mid); } else { add_node(index <<1|1, pos, mid+1, r); } TreeNode[index].nums = TreeNode[index<<1].nums + TreeNode[index<<1|1].nums; } long long query(int index, int l, int r) { long long sums = 0; int mid = 0; if (l== TreeNode[index].l and r == TreeNode[index].r) return TreeNode[index].nums; mid = (TreeNode[index].l + TreeNode[index].r) >> 1; if (mid >= r) return query(index<<1, l, r); else if ( l> mid) return query(index<<1|1, l, r); else return query(index<<1,l,mid)+ query(index<<1|1,mid+1, r); } }T; int main(int argc, char* argv[]){ while (cin >> n&&n) { long long ans = 0; T.init(); if (1 > n) break; for (int i=0; i<n; i++){ cin >> num[i].val; num[i].pos = i; } sort(num, num+n); T.build(1, 1, n); for (int i =0; i<n; i++){ ans += T.query(1, 1, n) - T.query(1, 1, num[i].pos+1); T.add_node(1, num[i].pos+1, 1, n); } printf("%lld\n", ans); } return 0; }转载于:https://www.cnblogs.com/tmortred/p/7921350.html
相关资源：数据结构—成绩单生成器