rmq稀疏表,O(log n)

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;   // 最大客栈数
int n, k, p;               // n: 客栈数；k: 色调数；p: 最高可接受消费
int a[MAXN], b[MAXN];      // a[i]: 色调；b[i]: 最低消费
int lg[MAXN];              // lg[i] = ⌊log2(i)⌋
int st[MAXN][18];          // 稀疏表 st[i][j]: 区间 [i, i+2^j-1] 的最小 b 值
vector<int> pos[50];       // 按色调分组，pos[c] 存放色调 c 的下标链表

// 预处理 lg 数组
void prlg(int nn){
    lg[1] = 0;
    for(int i = 2; i <= nn; ++i)
        lg[i] = lg[i>>1] + 1;
}

// 构建稀疏表
void build(){
    // 第 0 层：区间长度 1
    for(int i = 1; i <= n; ++i)
        st[i][0] = b[i];
    int L = lg[n];
    // 依次构建每一层 j，区间长度 2^j
    for(int j = 1; j <= L; ++j){
        int len = 1 << (j-1);
        for(int i = 1; i + (1<<j) - 1 <= n; ++i){
            st[i][j] = min(st[i][j-1], st[i+len][j-1]);
        }
    }
}

// 区间最小值查询 [l, r]
inline int qry(int l, int r){
    int len = r - l + 1;
    int j = lg[len];
    int seg = 1 << j;
    return min(st[l][j], st[r-seg+1][j]);
}

int main(){
    scanf("%d %d %d", &n, &k, &p);
    // 读入数据，按色调分组
    for(int i = 1; i <= n; ++i){
        scanf("%d %d", &a[i], &b[i]);
        pos[a[i]].push_back(i);
    }
    // 预处理和建表
    prlg(n);
    build();

    long long res = 0;
    // 对每个色调单独统计
    for(int c = 0; c < k; ++c){
        int sz = pos[c].size();
        if(sz < 2) continue;
        // 总共的配对数 C(sz,2)
        long long tot = 1LL * sz * (sz - 1) / 2;
        // 统计“无合法咖啡店”的不合法配对数
        long long inv = 0;
        for(int i = 0; i < sz; ++i){
            int lo = i + 1, hi = sz - 1, ma = i;
            // 二分找最远的 ma，使得区间 [pos[i], pos[ma]] 上 min b > p
            while(lo <= hi){
                int mid = (lo + hi) >> 1;
                if(qry(pos[c][i], pos[c][mid]) > p){
                    ma = mid;
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }
            inv += (ma - i);
        }
        // 累加合法配对
        res += (tot - inv);
    }

    printf("%lld\n", res);
    return 0;
}

双指针+二分

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k, p;
    cin >> n >> k >> p;
    vector<int> color(n+1), cost(n+1);
    for(int i = 1; i <= n; i++){
        cin >> color[i] >> cost[i];
    }

    // good[i] 表示第 i 个咖啡店费用是否 <= p
    vector<bool> good(n+2, false);
    for(int i = 1; i <= n; i++){
        if(cost[i] <= p) good[i] = true;
    }
    // nextGood[i] = 从 i 开始往右，第一个 good 的下标；如果没有，则为 n+1
    vector<int> nextGood(n+2, n+1);
    for(int i = n; i >= 1; i--){
        if(good[i]) nextGood[i] = i;
        else nextGood[i] = nextGood[i+1];
    }

    // 按颜色将下标收集
    vector<vector<int>> pos(k);
    for(int i = 1; i <= n; i++){
        pos[color[i]].push_back(i);
    }

    long long ans = 0;
    // 对于每个颜色列表，使用双指针或二分来统计满足条件的对
    for(int c = 0; c < k; c++){
        auto &idx = pos[c];
        int sz = idx.size();
        // 遍历列表中的每个位置
        for(int t = 0; t < sz; t++){
            int i = idx[t];
            int g = nextGood[i];
            // 在 idx[t+1..sz-1] 中找到第一个 >= g
            int l = t + 1, r = sz - 1, s = sz;
            while(l <= r){
                int mid = (l + r) >> 1;
                if(idx[mid] >= g){
                    s = mid;
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
            // 只要 idx[j] >= g 即可，且 j > t
            if(s < sz){
                ans += (sz - s);
            }
        }
    }

    cout << ans << "\n";
    return 0;
}

这题不需要使用rmq稀疏表