P3660 [USACO17FEB] Why Did the Cow Cross the Road III G

· · 题解

前言

这里提供一种 STL 加上二分的算法（个人认为对水平较低的人更加友好，比如说我）。

解法:

根据题意，其实可以将数字第一次出现与第二次出现的位置当做始末位置。而始末位置可以看成对应的一条线。

两根线相交的条件就是其中一根线的起点或终点的位置在另一根线的始末位置之间，而这根线的另一个点在另一条线的始末位置之外。

在读入时用结构体记录下每一对数字的始末位置，按照起始位置从大到小排序。

按照起始位置从大到小排序，这样就保证了当前起点一定在后面的所有线的起始位置之后。

然后我们倒序维护一个单调递增的数列。

从起点最靠前的线的终点开始不断加入这个数列，从起点位置排在第二的线开始，与当前线可以相交的线的数量，就是这根线的终点如果加入数列会排在的位置与起点如果加入数列会排在的位置之差。

因为终点加入之后的位置之前的线都是符合一个点在始末位置之外的线，而起点加入之后位置之后的线都是符合一个点在始末位置之间的线，只要两点都符合的线即为合法的相交，计入答案之内。

同时，因为维护的单调递增的数列只需要两个二分就能快速找到起点与终点应该存在的位置，所以总的用时符合数据范围。

注意需要边维护边计算，因为新插入的数字会改变原先的数列，导致如果先制造后计算的话没办法用 O(1) 的时间将该点删除（当然可能也有解决办法）。

代码：

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
int n,ans=0;
struct zwh{
    int l,r;
}a[50010],b[50010];
bool cmp(zwh x,zwh y){return x.l>y.l;}
vector<int> p;
int main(){
//  freopen("cross.in","r",stdin);
//  freopen("cross.out","w",stdout);

    cin>>n;
    for(int i=1;i<=n*2;i++){
        int x;
        cin>>x;
        if(a[x].l) a[x].r=i;
        else a[x].l=i;//记录始末位置 
    }
    sort(a+1,a+1+n,cmp);//按照起始位置排序 
    for(int i=n;i>=1;i--){
        if(!p.size()) p.push_back(a[i].r);//第一个终点，不用计算 
        else{
            int l1=lower_bound(p.begin(),p.end(),a[i].l)-p.begin();//计算起点应该排在的位置 
            int op=lower_bound(p.begin(),p.end(),a[i].r)-p.begin();//计算终点应该排在的位置 
            p.insert(p.begin()+op,a[i].r);//插入数据，维护一个递增的数列 
            ans+=op-l1;//加入合法数据 
        }
    }
    cout<<ans<<endl;

//  fclose(stdin);
//  fclose(stdout);
    return 0;
}