F - Jealous Two-二维逆序对

Time Limit: 2 sec / Memory Limit: 1024 MB

Score : 500500 points

Problem Statement

Snuke is planning on giving one gift each to Takahashi and Aoki.
There are NN candidates for the gifts. Takahashi's impression of the ii-th candidate is A_iAi​, and Aoki's impression of it is B_iBi​.

The two are very jealous. If Takahashi's impression of the gift Aoki gets is greater than Takahashi's impression of the gift Takahashi gets, Takahashi gets jealous of Aoki and starts fighting, and vice versa.

Among the N^2N2 possible ways of giving the gifts, how many do not lead to fighting?

Constraints

• 1 \leq N \leq 2\times 10^51≤N≤2×105
• 0 \leq A_i \leq 10^90≤Ai​≤109
• 0 \leq B_i \leq 10^90≤Bi​≤109
• All values in input are integers.

---

Input

Input is given from Standard Input in the following format:

NN
A_1A1​ \ldots… A_NAN​
B_1B1​ \ldots… B_NBN​

Output

Print the answer.

---

Sample Input 1 Copy

Copy

3
50 100 150
1 3 2

Sample Output 1 Copy

Copy

4

For example, if we give the 11-st candidate to Takahashi and the 22-nd candidate to Aoki, Takahashi's impression of the gift Aoki gets is 100100, while Takahashi's impression of the gift Takahashi gets is 5050, so Takahashi gets jealous of Aoki and starts fighting.

As another example, if we give the 33-rd candidate to Takahashi and the 22-nd candidate to Aoki, the two will not start fighting.

Note that it is allowed to give the same gift to the two.

---

Sample Input 2 Copy

Copy

3
123456789 123456 123
987 987654 987654321

Sample Output 2 Copy

Copy

6

---

Sample Input 3 Copy

Copy

10
3 1 4 1 5 9 2 6 5 3
2 7 1 8 2 8 1 8 2 8

Sample Output 3 Copy

Copy

37

求Ai>=Aj&&Bi<=Bj的 i,j

值得注意的是，i,j可以相等且没有大小限制

我们转化为逆序对求解，先按照B从小到大进行排序

这样就保证了Bi<=Bj  (i<=j)

然后我们给每个点分配排序好的坐标，类似于一维逆序对的原始坐标，再进行A从大到小排序，这样每当插入树状数组一个id,在其之前的小于等于id的A一定是大于等于它的。值得注意的是我们i==j的情况也算了一次，且没有重复。

但仍有 Ai=Aj Bi=Bj，i!=j 这种情况，我们只算了其中的二分之一

例如 1 1 1 

        2 2 2

我们在每次插入时i==j算了三次,i!=j 我们算了三次

但实际上i!=j还能够再组合三次  即， cnt*(cnt-1) 

我们第一次排序对b相同的采取a大的编号小，这样在对a进行排序时，一堆b相同的，a大的在前面，会被先加入小序号里面。否则会出现第一次排序之后，b相同的a大的编号大，在第二次排序时，一堆b相同的，a大的在前面，被加入到大序号里面，即bi<=bj虽然成立，ai>=aj也成立，但是排序之后就算不到这种情况了。

第二次排序时，a相同就把序号小的放在前面，而第一次排序之后a相同但是序号小的只能说明b更小，我们a大的放在前面，比它先放的要么比a大，要么==a.在一群相等的a里面，如果先放序号大的，也就是b更大的，无法保证后放的b更大也无法保证方案被完全统计

然后根据这一方案，我们会发现 1 1 1

                                                  2 2 2  

型被少算了一部分，所以还要加上

# include<iostream>
# include<map>
# include<vector>
# include<set>
# include<queue>
# include<math.h>
# include<cstring>
# include<iomanip>

# include<algorithm>

using namespace std;

# define mod 1000000007
typedef long long int ll;

typedef struct
{
    int id,a,b;

}xinxi;

xinxi s[200000+10];

bool cmp(xinxi a,xinxi b)
{
    if(a.b!=b.b)
    return a.b<b.b;

    return a.a>b.a;


}

bool cmp2(xinxi a,xinxi b)
{
    if(a.a!=b.a)
    return a.a>b.a;

    return a.id<b.id;


}

ll shu[200000+10];

int lowbit(int x)
{
    return (x)&(-x);

}
int n;

void change(int x)
{
    while(x<=n)
    {
        shu[x]++;

        x+=lowbit(x);

    }
}
map<pair<ll,ll>,ll>mp;

int getsum(int x)
{
    ll ans=0;

    while(x>0)
    {
        ans+=shu[x];

        x-=lowbit(x);

    }

    return ans;

}
int main ()
{


   cin>>n;

   for(int i=1;i<=n;i++)
   {
       cin>>s[i].a;
   }


   for(int i=1;i<=n;i++)
   {
       cin>>s[i].b;

       mp[make_pair(s[i].a,s[i].b)]++;

   }


   sort(s+1,s+1+n,cmp);

   for(int i=1;i<=n;i++)
   {
       s[i].id=i;

   }

   for(int i=1;i<=n;i++)
   {
       cout<<s[i].a<<" "<<s[i].b<<" "<<s[i].id<<endl;

   }

   sort(s+1,s+1+n,cmp2);



   ll ans=0;

   for(int i=1;i<=n;i++)
   {
       change(s[i].id);


       ans+=getsum(s[i].id);


   }




   for(auto it:mp)
   {
       ans+=(ll)(it.second)*(it.second-1)/2;

   }

   cout<<ans;


    return 0;

}