UVALive 4329 Ping pong
树状数组。考虑ai(从0开始,则i左边共i个,右边n-i-1个),左边有x个比他大的,i-x个比他小的,右边有y个比他大的,n-i-1-y个比他大的。交叉乘一下就得到了以ai为裁判的比赛总数。把所有人都枚举一遍,加在一起就是答案,会超int。如何才能知道ai左边有多少比他小的呢?假如aj<ai且j<i,用另一个数组b来标记这个数有没有出现过,那么b[aj] = 1;这样,比ai小的数的个数,就是b的前缀和。
#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<vector> #include<string> #include<queue> #include<cmath> ///LOOP #define REP(i, n) for(int i = 0; i < n; i++) #define FF(i, a, b) for(int i = a; i < b; i++) #define FFF(i, a, b) for(int i = a; i <= b; i++) #define FD(i, a, b) for(int i = a - 1; i >= b; i--) #define FDD(i, a, b) for(int i = a; i >= b; i--) ///INPUT #define RI(n) scanf("%d", &n) #define RII(n, m) scanf("%d%d", &n, &m) #define RIII(n, m, k) scanf("%d%d%d", &n, &m, &k) #define RIV(n, m, k, p) scanf("%d%d%d%d", &n, &m, &k, &p) #define RV(n, m, k, p, q) scanf("%d%d%d%d%d", &n, &m, &k, &p, &q) #define RFI(n) scanf("%lf", &n) #define RFII(n, m) scanf("%lf%lf", &n, &m) #define RFIII(n, m, k) scanf("%lf%lf%lf", &n, &m, &k) #define RFIV(n, m, k, p) scanf("%lf%lf%lf%lf", &n, &m, &k, &p) #define RS(s) scanf("%s", s) ///OUTPUT #define PN printf("\n") #define PI(n) printf("%d\n", n) #define PIS(n) printf("%d ", n) #define PS(s) printf("%s\n", s) #define PSS(s) printf("%s ", n) ///OTHER #define PB(x) push_back(x) #define CLR(a, b) memset(a, b, sizeof(a)) #define CPY(a, b) memcpy(a, b, sizeof(b)) #define display(A, n, m) {REP(i, n){REP(j, m)PIS(A[i][j]);PN;}} using namespace std; typedef long long LL; typedef pair<int, int> P; const int MOD = 100000000; const int INFI = 1e9 * 2; const LL LINFI = 1e17; const double eps = 1e-6; const double pi = acos(-1.0); const int N = 111111; const int M = 22; const int move[8][2] = {0, 1, 0, -1, 1, 0, -1, 0, 1, 1, 1, -1, -1, 1, -1, -1}; int a[N], b[N], c[N], n; void update(int x) { while(x <= N) { b[x]++; x += x & (-x); } } int sum(int x) { LL s = 0; while(x) { s += b[x]; x -= x & (-x); } return s; } int main() { //freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout); int t, k; LL ans; RI(t); while(t--) { RI(n); CLR(b, 0); REP(i, n) { RI(a[i]); c[i] = sum(a[i]); update(a[i]); } CLR(b, 0); ans = 0; FD(i, n, 0) { k = sum(a[i]); ans += LL(c[i]) * LL(n - i - 1 - k) + LL(i - c[i]) * LL(k); update(a[i]); } printf("%lld\n", ans); } return 0; }
补充:软件开发 , C++ ,