URAL - 1090 D - Inverse Order Pair——线段树求逆序数

URAL - 1090 D - Inverse Order Pair——线段树求逆序数

#include #include #include #include using namespace std;const int maxn = 1e5 + 10;int n, k, a[maxn], ans[maxn], res;struct Tree { int data[maxn<<1]; void init() { memset(data, 0, sizeof(data)); } void pushup(int root) { data[root] = data[root<<1] + data[root<<1|1]; } void updata(int l, int r, int root, int pos) { if (l == r) { data[root] += 1; return; } int mid = (l + r)>>1; if (pos <= mid) updata(l, mid, root<<1, pos); else updata(mid + 1, r, root<<1|1, pos); pushup(root); } int query(int l, int r, int root, int ql, int qr) { if (ql <= l && r <= qr) { return data[root]; } int mid = (l + r)>>1; int ans = 0; if (ql <= mid) ans += query(l, mid, root<<1, ql, qr); if (mid < qr) ans += query(mid + 1, r, root<<1|1, ql, qr); return ans; }}tree;int main() { while (~scanf("%d %d", &n, &k)) { res = 0; for (int i = 1; i <= k; i++) { for (int j = 1; j <= n; j++) scanf("%d", &a[j]); tree.init(); int sum = 0; for (int j = n; j >= 1; j--) { sum += tree.query(1, n, 1, 1, a[j]); tree.updata(1, n, 1, a[j]); } ans[i] = sum; res = max(res, sum); } for (int i = 1; i <= k; i++) { if (ans[i] == res) { printf("%d\n", i); break; } } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。