题解：SP4226 MSE06H - Japan

· · 题解

有一说一，这题翻译太好了，害的我看了好久才看懂。

前置芝士

思路分析

所以这题还是很简单的对不对，只要读懂了就行。

先想一想什么时候可以相交，显然只有 x_i<x_j 并且 y_i>y_j，或者 x_i>x_j 并且 y_i<y_j 的时候。

很眼熟对不对，这不就是逆序对吗！

接下来就很简单了了，按 x 排序，再来算 y 的逆序对即可。当然，暴力算肯定是不现实的，使用树状数组或归并排序即可。

还有一点值得注意：多测不清空，爆零两行泪！

然后就可以愉快的通过此题了。

AC Code

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>

using namespace std;

#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
char *p1,*p2,buf[1<<20+5];
inline int read(){
    int x=0;
    char c=gc();
    while(!isdigit(c)){
        c=gc();
    }while(isdigit(c)){
        x=x*10+(c^48);
        c=gc();
    }return x;
}

typedef long long LL;

const int N = 1000005;

int n, m, k;
int c[N];
LL res;

struct Kano
{
    int x, y;
}a[N];

bool cmp(Kano a, Kano b)
{
    if (a.x == b.x) return a.y < b.y;
    return a.x < b.x;
}

int lowbit(int x)
{
    return x & (-x);
}

LL sum(int x)
{
    LL sum = 0;
    for (int i = x; i > 0; i -= lowbit(i)) sum += c[i];
    return sum;
}

void upd(int x, int d)
{
    for (int i = x; i <= n; i += lowbit(i)) c[i] += d;
}

void init()
{
    res = 0;
    memset(c, 0, sizeof c);
}

int main()
{
    int T, f = 1;
    T = read();
    while (T -- )
    {
        init();
        n = read(), m = read(), k = read();
        for (int i = 1; i <= k; i ++ ) a[i].x = read(), a[i].y = read();

        sort(a + 1, a + k + 1, cmp);

        for (int i = k; i >= 1; i -- )
        {
            res += sum(a[i].y - 1);
            upd(a[i].y, 1);
        }
        printf("Test case %d: %lld\n", f, res);
        f ++ ;
    }
    return 0;
}