题意分析

这道题目描述了两个军队（蓝色和红色）的农民在攻城时投掷抓钩的情景。我们需要计算不同颜色农民的抓钩交叉的对数。

关键点：

1. 农民站成一排，位置编号1到n+m（n是蓝色农民数，m是红色农民数）
2. 每个农民投掷抓钩到城墙的某个位置（也是1到n+m）
3. 抓钩交叉的条件：
   • 如果两个农民的位置i < k，但抓钩位置j ≥ l
   • 或者i > k但j ≤ l
4. 同颜色的抓钩不会交叉
5. 不同颜色的抓钩如果投到同一位置也算交叉

解题思路

1. 问题转化：这实际上是一个计算逆序对的问题。我们可以将蓝色农民的(i,j)和红色农民的(k,l)看作点，计算满足交叉条件的对数。

2. 高效计算：

   • 对蓝色和红色农民分别按位置i排序
   • 使用归并排序的思想计算满足条件的对数
   • 或者使用树状数组/线段树来高效统计

3. 具体步骤：

   • 分别读取蓝色和红色农民的数据
   • 按位置i排序
   • 对于每个红色农民，统计有多少蓝色农民满足i < k且j ≥ l
   • 对于每个蓝色农民，统计有多少红色农民满足i > k且j ≤ l
   • 将两部分结果相加

标程（C++）

#include <iostream>
#include <cstdio>
#include <string.h>
#include <algorithm>
#define lowbit(x) (x&(-x))
using namespace std;
int n,m;
struct Node
{
    int x,y;
}pos[60005];
int a[60005];
void modify(int pos,int c)
{
    while(pos<=n+m)
    {
        a[pos]+=c;
        pos+=lowbit(pos);
    }
}
long long query(int pos)
{
    long long ans=0;
    while(pos>0)
    {
        ans+=a[pos];
        pos-=lowbit(pos);
    }
    return ans;
}
bool cmp(Node a,Node b)
{
    if(a.y==b.y)
        return a.x>b.x;
    return a.y<b.y;
}
int main()
{
    int t;
    scanf("%d",&t);
    for(int cas=1;cas<=t;cas++)
    {
        memset(a,0,sizeof(a));
        if(cas!=1)
            printf("\n");
        printf("Scenario #%d:\n",cas);
        int x,y;
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++)
            scanf("%d%d",&pos[i].x,&pos[i].y);
        for(int i=0;i<m;i++)
            scanf("%d%d",&pos[i+n].x,&pos[i+n].y);
        sort(pos,pos+n+m,cmp);
        long long ans=0;
        for(int i=0;i<n+m;i++)
        {
            modify(pos[i].x,1);
            ans+=pos[i].x-query(pos[i].x);
        }
        printf("%lld\n",ans);
    }
}