提出 #74619466

---

ソースコード 拡げる

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

struct Emp { int x, v, id; };
struct Query { int l, r, id; };

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, q; cin >> n >> q;
    vector<Emp> e(n);
    vector<int> vals;
    for(int i=0; i<n; ++i) {
        cin >> e[i].x >> e[i].v;
        vals.push_back(e[i].v);
    }
    sort(e.begin(), e.end(), [](Emp a, Emp b){ return a.x < b.x; });
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    for(int i=0; i<n; ++i) e[i].v = lower_bound(vals.begin(), vals.end(), e[i].v) - vals.begin();

    vector<Query> qs(q);
    for(int i=0; i<q; ++i) {
        int l, r; cin >> l >> r;
        qs[i].l = lower_bound(e.begin(), e.end(), l, [](Emp a, int val){ return a.x < val; }) - e.begin();
        qs[i].r = upper_bound(e.begin(), e.end(), r, [](int val, Emp a){ return val < a.x; }) - e.begin() - 1;
        qs[i].id = i;
    }

    int bs = max(1, (int)(n / sqrt(q + 1)));
    sort(qs.begin(), qs.end(), [bs](Query a, Query b){
        if(a.l/bs != b.l/bs) return a.l < b.l;
        return (a.l/bs % 2) ? (a.r < b.r) : (a.r > b.r);
    });

    vector<long long> ans(q);
    vector<int> cnt(vals.size(), 0);
    long long pairs = 0, k = 0; 
    auto add = [&](int i) {
        pairs += (k - cnt[e[i].v]); // total elements - those with same score = those with different score
        // Actually, we specifically need pairs where V_j > V_i. 
        // This is complex for Mo's. Let's use the simpler formula:
        // Sum of ranks = sum over all i (count of j such that V_j > V_i) + k
    };
    
    // Correction: Standard Competition Rank sum logic
    // Let f(v) be frequency of score v in range.
    // Sum = sum_{v} f(v) * ( (sum_{u > v} f(u)) + 1 )
    
    vector<int> f(vals.size(), 0);
    vector<int> bit(vals.size() + 1, 0);
    auto update_bit = [&](int idx, int val) {
        for(++idx; idx <= vals.size(); idx += idx & -idx) bit[idx] += val;
    };
    auto query_bit = [&](int idx) {
        int s = 0;
        for(++idx; idx > 0; idx -= idx & -idx) s += bit[idx];
        return s;
    };

    long long current_sum = 0;
    auto add_mo = [&](int i) {
        int small = query_bit(e[i].v - 1);
        int large = k - query_bit(e[i].v);
        current_sum += large; // i is the smaller one in 'large' pairs
        current_sum += small; // existing smaller ones now have a new 'larger' neighbor
        k++;
        f[e[i].v]++;
        update_bit(e[i].v, 1);
    };
    auto rem_mo = [&](int i) {
        update_bit(e[i].v, -1);
        f[e[i].v]--;
        k--;
        int small = query_bit(e[i].v - 1);
        int large = k - query_bit(e[i].v);
        current_sum -= large;
        current_sum -= small;
    };

    int L = 0, R = -1;
    for(auto& qry : qs) {
        while(R < qry.r) add_mo(++R);
        while(L > qry.l) add_mo(--L);
        while(R > qry.r) rem_mo(R--);
        while(L < qry.l) rem_mo(L++);
        ans[qry.id] = current_sum + k;
    }

    for(long long x : ans) cout << x << "\n";
    return 0;
}

提出情報

コンパイルエラー

./Main.cpp: In lambda function:
./Main.cpp:56:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for(++idx; idx <= vals.size(); idx += idx & -idx) bit[idx] += val;
      |                    ~~~~^~~~~~~~~~~~~~
./Main.cpp: In function 'int main()':
./Main.cpp:42:10: warning: variable 'add' set but not used [-Wunused-but-set-variable]
   42 |     auto add = [&](int i) {
      |          ^~~

ジャッジ結果