CF961E 追剧

1 CF961E 追剧

• 题目链接：https://codeforces.com/problemset/problem/961/e

2 题目描述

时间限制 \(2s\) | 空间限制 \(256M\)

有一天，\(Polycarp\) 决定重新观看著名电视剧 \(Tufurama\) 中他最喜欢的一集。当他搜索观看免费高清 \(Tufurama\) 的第 \(3\) 季第 \(7\) 集时只找到了第 \(7\) 季第 \(3\) 集。他很好奇如果有一天他想重新观看整个电视剧时却找不到想看的那一集怎么办？电视连续剧有 \(n\) 个季（从 \(1\) 到 \(n\)），第 \(i\) 个季节有 \(a_i\) 集(从 \(1\) 到 \(a_i\)）。\(Polycarp\) 认为，如果对于一些整数对 \(x\) 和 \(y\) \((x < y)\)，如果同时存在第 \(x\) 季第 \(y\) 集和第 \(y\) 季第 \(x\) 集，那么有一个搜索结果是错误的。帮助 \(Polycarp\) 计算出这种错误整数对的个数。

3 题解

我们发现：如果有一季的集数超过总季数，那么这些多余的集数肯定无法匹配，所以我们可以直接将这些季的集数设定为总季数。这样一来，数据范围就变成了两个 \(10^5\)。接着我们考虑：对于每一季来说，我们只需要统计所有小于等于集数的季中有多少季的集数大于等于当前这一季。

首先，我们来解决如何统计到小于等于集数的季。我们可以选择将所有的季复制出来一份副本，然后将该副本按照集数排序。我们以季为关键字从小到大枚举所有季，如果发现某一季正好等于当前集数，那么我们就可以查看在这一季及以前有多少季的集数大于等于当前集数对应的那一季。

那么我们如何找到有多少季的集数大于某一个季呢？我们很容易想到，可以用权值线段树维护集数，对于每一季，将其集数对应的在权值线段树的位置的权值 \(+1\)。查询时查询大于等于当前季的个数即可。

这里注意，我们有可能出现重复的情况，所以我们强制让当前这季的集数小于当前季。

4 代码（空格警告）：

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2e5+10;
#define int long long
int n, cnt, ans;
struct num
{
    int val, id;
}a[N], p[N];
struct node
{
    int l, r, sum, tag;
}t[N*4];
bool cmp(num x, num y)
{
    if (x.val == y.val) return x.id < y.id;
    return x.val < y.val;
}
void build(int p, int l, int r)
{
    t[p].l = l;
    t[p].r = r;
    if (l == r)
    {
        t[p].sum = 0;
        return ;
    }
    int mid = (l+r) / 2;
    build(p*2, l, mid);
    build(p*2+1, mid+1, r);
    t[p].sum = 0;
}
void pushdown(int p)
{
    if (t[p].tag)
    {
        t[p*2].tag += t[p].tag;
        t[p*2+1].tag += t[p].tag;
        t[p*2].sum += (t[p*2].r - t[p*2].l + 1) * t[p].tag;
        t[p*2+1].sum += (t[p*2+1].r - t[p*2+1].l + 1) * t[p].tag;
        t[p].tag = 0;
    }
}
void modify(int p, int l, int r)
{
    if (t[p].l >= l && t[p].r <= r)
    {
        t[p].sum += (t[p].r - t[p].l + 1);
        t[p].tag++;
        return ;
    }
    pushdown(p);
    int mid = (t[p].l + t[p].r) / 2;
    if (l <= mid) modify(p*2, l, r);
    if (r > mid) modify(p*2+1, l, r);
    t[p].sum = t[p*2].sum + t[p*2+1].sum;
}
int query(int p, int l, int r)
{
    if (t[p].l >= l && t[p].r <= r) return t[p].sum;
    pushdown(p);
    int mid = (t[p].l + t[p].r) / 2;
    int cans = 0;
    if (l <= mid) cans += query(p*2, l, r);
    if (r > mid) cans += query(p*2+1, l, r);
    return cans;
}
signed main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i].val, a[i].id = i;
        if (a[i].val > n) a[i].val = n;
    }
    for (int i = 1; i <= n; i++)
    {
        p[i].val = a[i].val;
        p[i].id = i;
    }
    sort(p+1, p+n+1, cmp);
    cnt = 1;
    build(1, 1, n);
    for (int i = 1; i <= n; i++)
    {
        if (i != 1) modify(1, min(i-1, a[i].val), min(i-1, a[i].val));
        while (i == p[cnt].val)
        {
            ans += query(1, p[cnt].id, n);
            cnt++;
        }
    }
    cout << ans;
    return 0;
}

欢迎关注我的公众号：智子笔记

CF961E 追剧

原文：https://www.cnblogs.com/david24/p/14406181.html