F - jealous two-dimensional reverse order pair

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

seek Ai>=Aj&&Bi<=Bj Of i,j

It is worth noting that ,i,j Can be equal without size restrictions

We convert it into reverse order pairs to solve , First according to B Sort from small to large

That's the guarantee Bi<=Bj  (i<=j)

Then we assign the sorted coordinates to each point , Similar to the original coordinates of one-dimensional inverse pairs , Proceed again A Sort from large to small , So whenever you insert a tree array id, Before it is less than or equal to id Of A It must be greater than or equal to it . It is worth noting that we i==j The situation is also calculated once , And there's no repetition .

But there are still Ai=Aj Bi=Bj,i!=j This situation , We only counted half of them

for example 1 1 1 

        2 2 2

We insert each time i==j Three times ,i!=j We calculated three times

But actually i!=j It can also be combined three times   namely , cnt*(cnt-1) 

We sort right for the first time b Take the same a Big numbers are small , This is right a When sorting , a pile b same ,a The big one is in front , Will be added to the small serial number first . Otherwise, after the first sorting ,b same a Big numbers are big , In the second sorting , a pile b same ,a The big one is in front , Be added to the big number , namely bi<=bj Although established ,ai>=aj It was also established , But this is not the case after sorting .

When sorting for the second time ,a If it is the same, put the small serial number in front , And after the first sorting a The same but small serial number can only indicate b smaller , We a The big ones are in the front , Put it before it or than a Big , or ==a. In a group of equal a Inside , If you put the large number first , That is to say b Bigger , There is no guarantee that it will be put back b There is no guarantee that the scheme will be completely counted

Then according to this plan , We will find that 1 1 1

                                                  2 2 2  

The type is underestimated , So we have to add

# 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;

}