洛谷 P3660 题解

admin 2021-05-02 AM 167℃ 0条

题目链接

前言

虽然解法重复了,但是我觉得这篇的讲解会比较清楚一些。

分析

首先,$a_i,b_i$ 可以看成一个区间 $[a_i,b_i)$。

所以,题目就是求相交的区间个数。(包含关系不算相交)

按照区间左端点排序,依次加入区间,加入时累加当前区间与之前区间相交的次数。

由于按左端点排序,如果 $j<i$ 且 $[a_j,b_j)$ 与 $[a_i,b_i)$ 相交,已经有 $a_j<a_i$,只需要 $a_i<b_j<b_i$ 即可。

也就是说,需要查询区间中有多少个数,还需要单点修改,考虑树状数组。

每一次 $ans \gets ans+sum(b_i-1)-sum(a_i)$,然后 $add(b_i)$ 即可。

时间复杂度 $O(n\log n)$。

解决

#include <algorithm>
#include <cstdio>
#include <iostream>

using namespace std;

const int N = 100005;
int n, tree[N];
struct Segment
{
    int l, r;
    bool operator<(const Segment &other) const
    {
        return l < other.l;
    }
} s[N];

inline void read(int &ret)
{
    char ch = getchar();
    ret = 0;
    while (ch < '0' || ch > '9')
        ch = getchar();
    while (ch >= '0' && ch <= '9')
        ret = ret * 10 + ch - '0', ch = getchar();
}

inline void add(int pos)
{
    while (pos <= n + n)
    {
        tree[pos]++;
        pos += pos & (-pos);
    }
}

inline int sum(int pos)
{
    int res = 0;
    while (pos)
    {
        res += tree[pos];
        pos &= pos - 1;
    }
    return res;
}

int main()
{
    read(n);
    for (int i = 1, x; i <= n + n; i++)
    {
        read(x);
        if (s[x].l)
            s[x].r = i;
        else
            s[x].l = i;
    }
    sort(s + 1, s + n + 1);
    long long ans = 0;
    for (int i = 1; i <= n; i++)
    {
        ans = ans + sum(s[i].r - 1) - sum(s[i].l);
        add(s[i].r);
    }
    cout << ans << endl;
    return 0;
}

THE END

标签: 妙妙题

非特殊说明,本博所有文章均为博主原创。

评论啦~