UVA1428 Ping pong

题目链接：​​传送门​​

权值比较小
直接建主席树
询问区间内小于等于一个数的数的个数
和大于等于一个数的个数
乘起来

#include <bits/stdc++.h>
#define
#define

using namespace std;
typedef long long ll;
int T, n, a[A], cnt, rt[A];
#define
#define
struct node {int l, r; ll siz;} tree[A * 5];
void insert(int l, int r, int L, int x, int &y) {
  tree[y = ++cnt] = tree[x]; tree[y].siz++;
  if (l == r) return;
  int mid = (l + r) >> 1;
  if (L <= mid) insert(l, mid, L, ls(x), ls(y));
  else insert(mid + 1, r, L, rs(x), rs(y));
}
ll query_small(int l, int r, int L, int x, int &y) {
  if (l == r) return tree[y].siz - tree[x].siz;
  int mid = (l + r) >> 1, w = tree[ls(y)].siz - tree[ls(x)].siz;
  if (L <= mid) return query_small(l, mid, L, ls(x), ls(y));
  else return query_small(mid + 1, r, L, rs(x), rs(y)) + w;
}
ll query_big(int l, int r, int L, int x, int &y) {
  if (l == r) return tree[y].siz - tree[x].siz;
  int mid = (l + r) >> 1, w = tree[rs(y)].siz - tree[rs(x)].siz;
  if (L <= mid) return query_big(l, mid, L, ls(x), ls(y)) + w;
  else return query_big(mid + 1, r, L, rs(x), rs(y));
}

int main(int argc, char const *argv[]) {
  cin >> T;
  while (T--) {
    memset(rt, 0, sizeof rt);
    memset(tree, 0, sizeof tree); cnt = 0;
    cin >> n; ll ans = 0;
    for (int i = 1; i <= n; i++) cin >> a[i], insert(1, 100000, a[i], rt[i - 1], rt[i]);
    for (int i = 1; i <= n; i++){
      ans += query_small(1, 100000, a[i], rt[0], rt[i - 1]) * query_big(1, 100000, a[i], rt[i], rt[n]);
      ans += query_big(1, 100000, a[i], rt[0], rt[i - 1]) * query_small(1, 100000, a[i], rt[i], rt[n]);
    }
    cout << ans << endl;
  }
  return 0;
}