[NOIP2011 提高组] 选择客栈

核心就是求某个区间的某种颜色的客栈数量

基础做法

$n\le 2\times {10}^5$、$k\le 50$

用前缀和来加速

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, k, p;
int sum[55][200005]; //同色前缀和
int a[200005];       //颜色
int b[200005];       //低消
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k >> p;
    for (int i = 1; i <= n; i++)
        cin >> a[i] >> b[i];
    int ans = 0;
    int lastP = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= k - 1; j++)
            sum[j][i] = sum[j][i - 1];
        sum[a[i]][i]++;
        if (b[i] <= p)
            lastP = i;
        if (lastP == i)
            ans += sum[a[i]][lastP] - 1;
        else
            ans += sum[a[i]][lastP];
    }
    cout << ans << "\n";
    return 0;
}

加强版

$n\le 2\times {10}^6$、$k\le {10}^4$

$O(n\log n)$

把每种颜色的下标存入动态数组，用二分来算区间数量。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 2000000;
const int MAXK = 10000;
int n, k, p;
vector<int> col[MAXK + 5]; // 颜色为 i 的客栈编号
int a[MAXN + 5];           // 颜色
int b[MAXN + 5];           // 低消
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k >> p;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i] >> b[i];
        col[a[i]].push_back(i);
    }
    int ans = 0;
    int lastP = 0;
    for (int i = 1; i <= n; i++)
    {
        if (b[i] <= p)
            lastP = i;
        int pos = upper_bound(col[a[i]].begin(),
                              col[a[i]].end(),
                              lastP) -
                  col[a[i]].begin();
        if (pos == 0)
            continue;
        pos--; // 最后一个大于等于 lastP 的同色下标
        if (col[a[i]][pos] == i)
            ans += pos;
        else
            ans += pos + 1;
    }
    cout << ans << "\n";
    return 0;
}

$O(n)$

既然每种颜色的下标有序，每次求的范围也是递增的，那么类似双指针的做法，在上次求到的位置往后看就好。

这样每个位置最多只被看一次。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 2000000;
const int MAXK = 10000;
int n, k, p;
vector<int> col[MAXK + 5]; // 颜色为 i 的客栈编号
int pos[MAXK + 5];         // 下一次从哪个位置开始看
int a[MAXN + 5];           // 颜色
int b[MAXN + 5];           // 低消
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k >> p;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i] >> b[i];
        col[a[i]].push_back(i);
    }
    int ans = 0;
    int lastP = 0;
    for (int i = 1; i <= n; i++)
    {
        if (b[i] <= p)
            lastP = i;
        // 颜色 a[i] 的当前位置没超过范围、且再 lastP 之前、且不是 i
        // 就往后挪
        while (pos[a[i]] < col[a[i]].size() &&
               col[a[i]][pos[a[i]]] <= lastP &&
               col[a[i]][pos[a[i]]] != i)
            pos[a[i]]++;
        ans += pos[a[i]];
    }
    cout << ans << "\n";
    return 0;
}