【XJOI】燃烧的远征

题目链接

燃烧的远征

题目描述：

为了抵御托伦星人的进攻，Hammerhead的母公司，腐朽的星际托拉斯GTD的CEO TS派出了保安舰队的主力远征，并选拔出了GTD精英组成的小队前往战地前沿作战。据CEO了解到的情报，托伦星人的首领——叫兽?杨拥有一种叫做“电击”的可怕技能，此技能能够在瞬间置人于死地。谢天谢地的是，GTD众信仰两个神：C神和Z神。对C神的特别忠诚的能够死后原地复活，信仰越坚定，复活后状态恢复得越满；对Z神的特别忠诚的能够利用高分贝噪音对叫兽?杨进行攻击，信仰越坚定，伤害输出越高。
在C神和Z神的庇佑下，GTD精英小队对托伦星人展开了作战。
这场燃烧的远征是否会由GTD取得最后的胜利呢？又或者由于叫兽?杨的可怕能力，末日的回响响个没完，这场战争终会历时千年呢？

对精英小队的所有队员（一共N名），CEO按照他们对C神和Z神忠诚度进行了两个评分。对C神最忠诚的评分为\(N\)，第二忠诚的为\(N-1\)……最不忠诚的评分为1。对Z神的忠诚程度也按照这样的标准进行评分。
CEO决定先挑选两人作为先锋对叫兽?杨进行攻击。为了保证队伍的平衡性，CEO要求两人小队的成员应该要满足这样的条件：如果某位成员对C神的忠诚度高于另一位，则他对Z神的忠诚度必须要低于另一位；如果某位成员对C神的忠诚度低于另一位，则他对Z神的忠诚度必须要高于另一位。
现在，CEO希望找出一共有多少种可能的选择。

输入格式：

文件输入。输入文件名tbc.in
输入第一行为\(N\)，即小队成员总数。
接下来的\(N\)行，每行两个数表示每个成员的忠诚度——第一个数为对C神的忠诚度，第二个数为对Z神的忠诚度。

输出格式：

文件输出。输出文件名tbc.out
输出仅一行，为符合条件的两人组合的总数。

样例输入：

5
5 4
3 2
4 3
1 5
2 1

样例输出：

4

数据范围：

对50%的数据，\(N≤1000\)
对100%的数据，\(N≤100000\)

时间限制：

2s

提示：

可能的组合有：
第一位（5 4）和第四位（1 5）
第二位（3 2）和第四位（1 5）
第三位（4 3）和第四位（1 5）
第四位（1 5）和第五位（2 1）

【特别感谢】
乔?霍尔德曼：《千年战争》
玻璃渣：山口山
Ural：acm.timus.ru
GTD：众人

题解

题意是有\(N\)个人，每个人有两个数值，先暂且设这两个数为\(x\)和\(y\)
要求找出两个人，使得\(x_1>x_2\)且\(y_1<y_2\)，
这不就是求逆序对的个数吗。
众所周知，我们可以先把所有人按照\(x\)，从小到大排序，然后用msort求逆序对的个数。
如何用msort求逆序对我就不详解了，大家可以看代码理解。
注意这里\(N\)的取值范围是\(N≤100000\)，而逆序对的个数的数量级是\(N^2\)的，所以\(ans\)需要用\(long long\)才存的下。
时间复杂度为\(O(NlogN)\)
msort求逆序对：

#include<bits/stdc++.h>
using namespace std;
int n,x,y;
long long ans;
int a[100009];
void msort(int l,int r){
    if(l==r) return;
    int mid=(l+r)/2;
    msort(l,mid);
    msort(mid+1,r);
    int j=l,i=mid+1;
    while(j<=mid || i<=r){
        while(j>mid && i<=r)i++;
        if(j>mid && i>r) break;
        while(j<=mid && i>r)j++;
        if(j>mid && i>r) break;
        if(a[j]<=a[i]) j++;
        else{
            ans+=mid-j+1;
            i++;
        }
    }
    sort(a+l,a+r+1);
}
int main(){
    scanf("%d",&n);
    for(int j=1;j<=n;j++){
        scanf("%d%d",&x,&y);
        a[x]=y;
    }
    msort(1,n);
    printf("%lld",ans);
    return 0;
}

其实求逆序对的方法不止有用msort求这一种，
利用树状数组我们也可以实现求逆序对。
我们可以先把所有人按照\(x\)从大到小排序，（这里从大到小是为了后面加入数时方便一点，如果这里从小到大，后面可以倒着加入每个数）
我们从1到\(N\)依次加入每个人，
每次我们在树状数组上把\(a[y]++\)，
在加入每个数之前我们求\(y-1\)的前缀和加到\(ans\)里。
树状数组求逆序对的时间复杂度也是\(O(NlogN)\)
树状数组求逆序对：

#include<bits/stdc++.h>
using namespace std;
int n,x,y;
long long ans;
struct aa{
    int x,y;
}a[100009];
int p[400009];
bool cmp(aa x,aa y){
    return x.x>y.x;
}
int lb(int x){
    return x&(-x);
}
void add(int x){
    int u=x;
    while(u<=400000){
        p[u]++;
        u+=lb(u);
    }
}
int fd(int x){
    int ans=0;
    while(x){
        ans+=p[x];
        x-=lb(x);
    }
    return ans;
}
int main(){
    scanf("%d",&n);
    for(int j=1;j<=n;j++)
        scanf("%d%d",&a[j].x,&a[j].y);
    sort(a+1,a+n+1,cmp);
    for(int j=1;j<=n;j++){
        ans+=fd(a[j].y);
        add(a[j].y);
    }
    printf("%lld",ans);
    return 0;
}

【XJOI】燃烧的远征

原文：https://www.cnblogs.com/linjiale/p/11317703.html