Why Did the Cow Cross the Road III（树状数组）

Why Did the Cow Cross the Road III

时间限制: 1 Sec  内存限制: 128 MB
提交: 65  解决: 28
[提交][状态][讨论版]

题目描述

The layout of Farmer John's farm is quite peculiar, with a large circular road running around the perimeter of the main field on which his cows graze during the day. Every morning, the cows cross this road on their way towards the field, and every evening they all cross again as they leave the field and return to the barn. 
As we know, cows are creatures of habit, and they each cross the road the same way every day. Each cow crosses into the field at a different point from where she crosses out of the field, and all of these crossing points are distinct from each-other. Farmer John owns N cows, conveniently identified with the integer IDs 1…N, so there are precisely 2N crossing points around the road. Farmer John records these crossing points concisely by scanning around the circle clockwise, writing down the ID of the cow for each crossing point, ultimately forming a sequence with 2N numbers in which each number appears exactly twice. He does not record which crossing points are entry points and which are exit points.

Looking at his map of crossing points, Farmer John is curious how many times various pairs of cows might cross paths during the day. He calls a pair of cows (a,b) a "crossing" pair if cow a's path from entry to exit must cross cow b's path from entry to exit. Please help Farmer John count the total number of crossing pairs.

输入

The first line of input contains N (1≤N≤50,000), and the next 2N lines describe the cow IDs for the sequence of entry and exit points around the field.

输出

Please print the total number of crossing pairs.

样例输入

4
3
2
4
4
1
3
2
1

样例输出

3
【题意】在一个圆上，顺时针 给出一些数字，每个数字出现两遍，然后数字相同的连边，问多少对边相交。
【分析】我们可以发现按照题目给出的数据顺序，如果两个数的连线相交，那么他俩在一维中的连线一相交，也就是如果某个数两次出现
 的位置中间有多少个数 出现了一次，那么就有多少条线与他相交，那我们直接对于每个数统计两个位置之间的出现一次的数就行了。
 对于这种数据量较大无法N方解决的统计问题，树状数组一般都可以。对于这个题，从左到右扫，当第一次扫到这个数时，从这个位置
 向上lowbit依次+1，当第二次扫到这个数的时候，统计第一次出现的位置到当前位置的sum值，然后从第一次出现的位置向上lowbit
 依次-1，表示删除此边。

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define met(a,b) memset(a,b,sizeof a)
#define pb push_back
#define mp make_pair
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int N = 1e5+50;
const int mod = 1e9+7;
const double pi= acos(-1.0);
typedef pair<int,int>pii;
int n,ans;
int a[N],sum[N],vis[N];
void upd(int x,int add){
    for(int i=x;i<=2*n;i+=i&(-i)){
        sum[i]+=add;
    }
}
int qry(int x){
    int ret=0;
    for(int i=x;i>=1;i-=i&(-i)){
        ret+=sum[i];
    }
    return ret;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=2*n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=2*n;i++){
        if(!vis[a[i]]){
            upd(i,1);
            vis[a[i]]=i;
        }
        else {
            int s=qry(i-1)-qry(vis[a[i]]);
            //printf("i:%d ai:%d l:%d r:%d
",i,a[i],qry(vis[a[i]]),qry(i-1));
            ans+=s;
            upd(vis[a[i]],-1);
        }
    }
    printf("%d
",ans);
    return 0;
}