E题无脑求逆序对解法代码

有人问怎么无脑求逆序对过

因为是两个log，所以需要一定的常数优化小技巧

1. 树状数组写一个快捷清理的功能
2. 不要用动态开点数据结构，需要离散化

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int INF = 1000000001;
template<typename T>
void discretize(vector<T> &v)
{
    vector<T> ordered = v;
    sort(ordered.begin(), ordered.end());
    ordered.erase(unique(ordered.begin(), ordered.end()), ordered.end());
    for (auto &val: v)
    {
        val = T(lower_bound(ordered.begin(), ordered.end(), val) - ordered.begin() + 1);
    }
}
class FenwickTree
{
public:
    FenwickTree(int n) : n(n), bit(n + 1, 0), vis(n + 1, 0)
    {}
    void add(int idx, int value)
    {
        while (idx <= n)
        {
            if (!vis[idx])
            {
                vis[idx] = 1;
                stk.push_back(idx);
            }
            bit[idx] += value;
            idx += idx & -idx;
        }
    }
    int query(int idx)
    {
        int sum = 0;
        while (idx > 0)
        {
            sum += bit[idx];
            idx -= idx & -idx;
        }
        return sum;
    }
    void clear()
    {
        while (!stk.empty())
        {
            int idx = stk.back();
            stk.pop_back();
            bit[idx] = 0;
            vis[idx] = 0;
        }
    }
private:
    int n;
    vector<int> bit;
    vector<int> vis;
    vector<int> stk;
};
long long count_pairs(FenwickTree &ft, vector<long long> &v)
{
    int n = (int) v.size();
    long long result = 0;
    // 清空树状数组
    ft.clear();
    // 离散化处理
    discretize(v);
    // 遍历每个元素，使用树状数组统计
    for (int i = n - 1; i >= 0; --i)
    {
        result += ft.query((int) v[i]); // 统计小于等于 v[i]-1 的元素个数
        ft.add((int) v[i], 1); // 更新树状数组
    }
    return result;
}
/*
3 1
0 1
2 -1
9 -1
3 2
0 1
2 -1
9 -1
3 3
0 1
2 -1
9 -1
3 5
0 1
2 -1
9 -1
*/
int main()
{
    int n;
    long long k;
    scanf("%d %lld", &n, &k);
    vector<pair<long long, long long>> a(n);//p v
    vector<long long> temp(n);
    FenwickTree ft(n);
    for (int i = 0; i < n; ++i)
    {
        scanf("%lld %lld", &a[i].first, &a[i].second);
    }
    sort(a.begin(), a.end(), [](const auto &A, const auto &B)
    {
        return A.first < B.first;
    });
    int l = 0, r = INF, ans = 0;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        for (int i = 0; i < n; ++i)
        {
            temp[i] = a[i].first * 2 + a[i].second * mid;
        }
        auto nowk = count_pairs(ft, temp);
        if (nowk >= k)
        {
            r = mid - 1;
        } else
        {
            ans = mid;
            l = mid + 1;
        }
    }
    if (ans == INF)
    {
        printf("No\n");
        return 0;
    }
    ans++;
    printf("Yes\n%d.%c00000\n", ans / 2, "05"[ans & 1]);
    return 0;
}