树状数组求调,调的道心奔溃了
查看原帖
树状数组求调,调的道心奔溃了
588080
n_bluetea楼主2024/6/24 17:34
#include <bits/stdc++.h>
using namespace std;

#define int long long
const int maxn = 200005; // 确保maxn足够大

int n;
int wz[maxn]; // 树状数组,用于存储元素出现次数
int yy[maxn]; // 树状数组,用于存储元素的坐标和

struct node {
    int x, v;
} a[maxn];

// 按照价值从大到小排序
bool cmp(node a, node b) {
    return a.v > b.v;
}

// 计算lowbit
int lowbit(int x) {
    return x & (-x);
}

// 在位置x上增加一个元素
void add_num(int x) {
    for (int i = x; i < maxn; i += lowbit(i)) {
        wz[i]++;
    }
}

// 计算前x个元素的数量和
int sum_num(int x) {
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) {
        res += wz[i];
    }
    return res;
}

// 在位置x上增加坐标值v
void add_coord(int x, int v) {
    for (int i = x; i < maxn; i += lowbit(i)) {
        yy[i] += v;
    }
}

// 计算前x个坐标的和
int sum_coord(int x) {
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) {
        res += yy[i];
    }
    return res;
}

void run() {
    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> a[i].v >> a[i].x;
    }

    sort(a + 1, a + n + 1, cmp);

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        int x = a[i].x;
        int v = a[i].v;

        int sumLeftNum    = sum_num(x - 1);
        int sumLeftCoord  = sum_coord(x - 1);
        int sumRightNum   = sum_num(maxn) - sum_num(x);
        int sumRightCoord = sum_coord(maxn) - sum_coord(x);

        ans += v * (x * sumLeftNum - sumLeftCoord) + v * (sumRightCoord - x * sumRightNum);

        add_coord(x, x);
        add_num(x);
        
    }
    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T--) {
        run();
    }
    return 0;
}

2024/6/24 17:34
加载中...