小记:题目数据都不给,出题人就是打算在题意上坑人
小记:求逆序对,离散化一下,不晓得它的值可以多大,离散化之后对其数组排序,然后再从头开始用树状数组求每个点前面id比它大的值,
还好题目提示了一句,不会有重复学号的,省了一步,这一句是看的最懂的了。
poj 2299是和这个差不多的题,不过有重复的而已。
代码:
#include <iostream> #include <stdio.h> #include <string.h> #include <math.h> #include <stdlib.h> #include <map> #include <set> #include <vector> #include <stack> #include <queue> #include <algorithm> using namespace std; #define mst(a,b) memset(a,b,sizeof(a)) #define eps 10e-8 const int MAX_ = 1000010; const int N = 100010; const int INF = 0x7fffffff; struct node { int id, v; }a[MAX_]; int C[MAX_]; inline int lowbit(int x){ return x&(-x); } inline void add(int x,int num){ while(x < MAX_){ C[x] += num; x += lowbit(x); } } inline int sum(int x){ int cnt = 0; while(x > 0){ cnt += C[x]; x -= lowbit(x); } return cnt; } int cmp(const node& a, const node& b ){ return a.v < b.v; } int main(){ int n; long long ans; while(scanf("%d",&n) != EOF){ for(int i = 1; i <= n; ++i){ scanf("%d",&a[i].v); a[i].id = i; } mst(C,0); sort(a+1,a+n+1,cmp); ans = 0; for(int i = n; i > 0; --i){ ans += sum(a[i].id); add(a[i].id, 1); } printf("%I64d\n",ans); } return 0; }