Why Did the Cow Cross the Road III (G)

题意：求相交区间的个数。

思路

---

思路1：直接考虑每个数对应区间的贡献，显然相交区间的要求就是对于区间$[l,r]$，与左边相交或者与右边相交，又因为不讲顺序，所以可以考虑对所有区间按左端点排序，然后对于当前区间我们只需要找到右端点在$[l,r]$之间的数就行了，因为排序后左端点必定小于等于$l$。因此可以用$BIT$进行区间查询。

---

思路2：逆向思维，即用所有情况$-$不满足条件的。

所有情况$=\dfrac{n(n-1)}{2}$。

不满足条件的即：对于区间$[l,r]$，存在一个区间在该区间外，或者被该区间包括，这里可以用两个$BIT$分别维护左端点和右端点，每次遍历到一个区间的右端点时，就计算该区间左端点左边有多少个右端点，然后计算有多少个右端点在$(l,r)$之内。

---

时间复杂度：$O(nlogn)$

代码

代码1

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
#define lowbit(x) x&(-x)
int n,p[N],cnt[N];
struct BIT{
    int tr[N];
    void upd(int x,int k){
    while(x<=(n<<1)){
        tr[x]+=k;
        x+=lowbit(x);
    }
}
int que(int x){int s=0;
    while(x){
        s+=tr[x],x-=lowbit(x); 
    }return s;
}
}t1,t2;
int main(){
    scanf("%d",&n);
    ll ans=1LL*n*(n-1)/2;
    for(int i=1,x;i<=(n<<1);i++){
        scanf("%d",&x);
        if(++cnt[x]==2){
            ans-=(0LL+t1.que(p[x]-1)+t2.que(i-1)-t2.que(p[x]));
            t1.upd(i,1),t2.upd(p[x],1);
        }p[x]=i;
    }
    printf("%lld\n",ans); 
    return 0;
}

代码2：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
#define lowbit(x) x&(-x)
int n,vis[N];
PII p[N];
struct BIT{
    int tr[N];
    void upd(int x,int k){
    while(x<=(n<<1)){
        tr[x]+=k;
        x+=lowbit(x);
    }
}
int que(int x){int s=0;
    while(x){
        s+=tr[x],x-=lowbit(x); 
    }return s;
}
}t;
int main(){
    scanf("%d",&n);
    ll ans=0;int id=0;
    for(int i=1,x;i<=(n<<1);i++){
        scanf("%d",&x);
        if(!vis[x]) vis[x]=i;
        else p[++id].fi=vis[x],p[id].se=i;
    }
    sort(p+1,p+n+1);
    for(int i=1;i<=n;i++){
        ans+=t.que(p[i].se)-t.que(p[i].fi-1);
        t.upd(p[i].se,1);
    }printf("%lld\n",ans);
    return 0;
}