【题解】[USACO17FEB]Why Did the Cow Cross the Road III G

2022-05-22

题目背景

给定长度为2N的序列，1~N各处现过2次，i第一次出现位置记为ai，第二次记为bi，求满足ai<aj<bi<bj的对数

题目描述

The layout of Farmer John's farm is quite peculiar, with a large circular road running around the perimeter of the main field on which his cows graze during the day. Every morning, the cows cross this road on their way towards the field, and every evening they all cross again as they leave the field and return to the barn.

As we know, cows are creatures of habit, and they each cross the road the same way every day. Each cow crosses into the field at a different point from where she crosses out of the field, and all of these crossing points are distinct from each-other. Farmer John owns $N$ cows, conveniently identified with the integer IDs $1 \ldots N$ , so there are precisely $2N$ crossing points around the road. Farmer John records these crossing points concisely by scanning around the circle clockwise, writing down the ID of the cow for each crossing point, ultimately forming a sequence with $2N$ numbers in which each number appears exactly twice. He does not record which crossing points are entry points and which are exit points.

Looking at his map of crossing points, Farmer John is curious how many times various pairs of cows might cross paths during the day. He calls a pair of cows $(a,b)$ a "crossing" pair if cow $a$ 's path from entry to exit must cross cow $b$ 's path from entry to exit. Please help Farmer John count the total number of crossing pairs.

输入格式

The first line of input contains $N$ ( $1 \leq N \leq 50,000$ ), and the next $2N$ lines describe the cow IDs for the sequence of entry and exit points around the field.

输出格式

Please print the total number of crossing pairs.

样例 #1

样例输入 #1

样例输出 #1

思路

这种涉及到大小关系的题目有一种套路，就是先固定好其中一个大小顺序。比如说，这道题就可以先固定 $a_i$ 的大小顺序，处理出每个 $i$ 的 $a_i,b_i$ 后，按 $a_i$ 从小到大排序。则只需要考虑 $a_j < b_i < b_j$ 了。因为 $i<j$ （排过序了），所以用树状数组维护 $b_i$ 的个数，每次求出 $a_j$ 和 $b_j$ 之间的 $b_i$ 个数就行了。

代码

#include <cstdio>
#include <algorithm>
#define MAXN 50000
#define lowbit(x) ((x) & -(x))
struct Node {
    int a, b;
    bool operator<(const Node &rhs) const{
        if (a == rhs.a)
            return b < rhs.b;
        return a < rhs.a;
    }
} p[MAXN + 3];
int n, c[(MAXN << 1) + 3], ans;
void update(int x, int k) {
    while (x <= (n << 1))
        c[x] += k, x += lowbit(x);
}
int query(int x) {
    int s = 0;
    while (x >= 1)
        s += c[x], x -= lowbit(x);
    return s;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= (n << 1); i++) {
        int x;scanf("%d", &x);
        if (p[x].a)
            p[x].b = i;
        else
            p[x].a = i;
    }
    std::sort(p + 1, p + 1 + n);
    for (int i = 1; i <= n; i++)
        ans += query(p[i].b - 1) - query(p[i].a), update(p[i].b, 1);
    printf("%d\n", ans);
    return 0;
}