题解：CF1762F Good Pairs

· · 题解

题意： 已知一个由 n 个整数组成的数组 a 和一个整数 k。

一对整数 (l,r) 是好的，如果存在索引序列 i_1,i_2,…,i_m 使得

  2. 对于所有 1≤j<m，满足 i_j<i_{j+1}； 

求好整数对 (l,r)(1≤l≤r≤n) 的个数。

题解： 线段树 + 数组索引。


#include "stdafx.h"

#include<set>
#include<map>
#include<list>
#include<cmath>
#include<queue>
#include<stack>
#include<deque>
#include<vector>
#include<random>
#include<string>
#include<cstdio>
#include<bitset>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>


using namespace std;
#define ll   long long
//typedef long long ll;

const int N = 500000 + 5, M = 100000, MAX = 0x3f3f3f3f;
int n, k, a[N], b[100005], dp[N], MIN[M << 2], SUM[M << 2];

#define mid ((l + r) >> 1)
#define lson (x << 1)
#define rson ((x << 1) | 1)
//   modify_min(1, 1, M, a[i], i); 保存数据的最小下标
void modify_min(int x, int l, int r, int pos, int v) {
    if (l == r) {
        MIN[x] = v;
        return;
    }
    if (pos <= mid) modify_min(lson, l, mid, pos, v);
    else modify_min(rson, mid + 1, r, pos, v);
    MIN[x] = min(MIN[lson], MIN[rson]);
}
//     query_min(1,    1,    M, a[i] + 1, a[i] + k);
int query_min(int x, int l, int r, int L, int R) {
    if (l > R || r < L) return MAX;
    if (l >= L && r <= R) return MIN[x];
    return min(query_min(lson, l, mid, L, R), query_min(rson, mid + 1, r, L, R));
}
// modify_sum(1, 1, M, a[i], 1); 保存 数据的个数
void modify_sum(int x, int l, int r, int pos, int v) {
    if (l == r) {
        SUM[x] += v;
        return;
    }
    if (pos <= mid) modify_sum(lson, l, mid, pos, v);
    else modify_sum(rson, mid + 1, r, pos, v);
    SUM[x] = SUM[lson] + SUM[rson];
}
int query_sum(int x, int l, int r, int L, int R) {
    if (l > R || r < L) return 0;
    if (l >= L && r <= R) return SUM[x];
    return query_sum(lson, l, mid, L, R) + query_sum(rson, mid + 1, r, L, R);
}

void clear() {
    for (int i = 1; i <= n; i++) {
        dp[i] = 0;
        b[a[i]] = 0;
        modify_min(1, 1, M, a[i], MAX);
        modify_sum(1, 1, M, a[i], -1);// 抵消原来的加1
    }
}
ll solve() {
    ll ret = 0;
    for (int i = n; i > 0; i--) {
        // 只考虑大于a[i]的数据
        int j = query_min(1, 1, M, a[i] + 1, a[i] + k);
        // dp[j]的每个好整数对加上a[i]仍然是好整数对， a[i]与[a[i] + 1, a[j]]中的每个数据 组成好整数对
        if (j != MAX) dp[i] = dp[j] + query_sum(1, 1, M, a[i] + 1, a[j]),
            cout<<"a[i] + 1="<<a[i] + 1<<", a[i] + k="<<a[i] + k<<", a[j]="<<a[j]<<endl,
         cout<<"MAX="<<MAX<<", j="<<j<<", dp[j]="<<dp[j]<<", dp[i]="<<dp[i]<<endl;
        modify_min(1, 1, M, a[i], i);
        modify_sum(1, 1, M, a[i], 1);
        ret += dp[i];
            cout<<"i="<<i<<", ret="<<ret<<endl;
    }
    return ret;
}
void rmain() {
    scanf_s("%d %d", &n, &k);
    for (int i = 1; i <= n; i++) scanf_s("%d", &a[i]);
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        b[a[i]]++;
        ans += b[a[i]];// 从 the first test case，可以知道这个公式的正确性
    }
    cout<<"ans="<<ans<<endl;
    /*reverse(a + 1, a + n + 1);
     modify_min(1, 1, M, a[4], 4);
     modify_min(1, 1, M, a[3], 3);
     modify_min(1, 1, M, a[2], 2);
     int j=query_min(1, 1, M, 7, 9);
     cout<<"j="<<j<<endl;*/
    ans += solve();// 只统计升序的好整数对
    clear();

    cout<<"ans="<<ans<<endl;
    reverse(a + 1, a + n + 1);
    for (int i = 1; i <= n; ++i) cout<<"  "<<a[i];
    cout<< endl;
    ans += solve();
    clear();
    printf("%lld\n", ans);
}

int main() {
    int T;

    FILE *fi;
    freopen_s(&fi,"CF1762Fin.txt","r",stdin);


     // 使用 0x3f3f3f3f 初始化线段树
    memset(MIN, 0x3f, sizeof MIN);
    scanf_s("%d", &T);
    while (T--) {
        rmain();
    }
    return 0;
}