Pair of Topics CodeForces - 1324D（逆序+树状数组）

The next lecture in a high school requires two topics to be discussed. The i-th topic is interesting by ai units for the teacher and by bi units for the students.

The pair of topics i and j (i<j) is called good if ai+aj>bi+bj (i.e. it is more interesting for the teacher).

Your task is to find the number of good pairs of topics.

Input
The first line of the input contains one integer n (2≤n≤2⋅105) — the number of topics.

The second line of the input contains n integers a1,a2,…,an (1≤ai≤109), where ai is the interestingness of the i-th topic for the teacher.

The third line of the input contains n integers b1,b2,…,bn (1≤bi≤109), where bi is the interestingness of the i-th topic for the students.

Output
Print one integer — the number of good pairs of topic.

Examples
Input
5
4 8 2 6 2
4 5 4 1 3
Output
7
Input
4
1 3 2 4
1 3 2 4
Output
0
思路：由于i<j，所以我们从后往前来，这样就可以了。题目要求ai+aj>bi+bj，那么也就是ai-bi>bj-aj。由于有可能是负数，因此我们离散化bj-aj，然后随时更新到树状数组中，然后对于每一个ai-bi求树状数组中有多少个数小于它。注意开 long long。
代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxx=2e5+100;
struct node{
int x;
int y;
}p[maxx];
int c[maxx];
int a[maxx];
int n;
inline int lowbit(int x){return x&-x;}
inline void update(int x,int v)
{
while(x<maxx)
{
c[x]+=v;
x+=lowbit(x);
}
}
inline int query(int x)
{
int sum=0;
while(x)
{
sum+=c[x];
x-=lowbit(x);
}
return sum;
}
int main()
{
scanf("%d",&n);
memset(c,0,sizeof(c));
for(int i=1;i<=n;i++) scanf("%d",&p[i].x);
for(int i=1;i<=n;i++) scanf("%d",&p[i].y);
for(int i=1;i<=n;i++) a[i]=p[i].y-p[i].x;
sort(a+1,a+1+n);
ll ans=0,num;
for(int i=n;i>=1;i--)
{
num=p[i].x-p[i].y;
int pos=lower_bound(a+1,a+1+n,num)-a;
ans+=(ll)query(pos-1);
pos=lower_bound(a+1,a+1+n,p[i].y-p[i].x)-a;
update(pos,1);
}
cout<<ans<<endl;
return 0;
}

努力加油a啊，(^o)/~

最后

以上就是苗条白云最近收集整理的关于Pair of Topics CodeForces - 1324D（逆序+树状数组）的全部内容，更多相关Pair内容请搜索靠谱客的其他文章。