CodeForces - 1324 D. Pair of Topics
原题地址：
/contest/1324/problem/D
基本题意：
给你一个数组，找符合（i < j）ai + aj > bi + bj 的序列对的数量。
基本思路：
本质上我们设 ci = ai - bi 那么原式可以换为 ci + cj > 0，所以我们可以有几个思路：
pbds黑科技解法，我们转换为 cj > -ci 直接上红黑树每次插入 -ci 暴力往前找rank；
#include <bits/stdc++.h>#include <bits/extc++.h>using namespace std;using namespace __gnu_pbds;#define IO std::ios::sync_with_stdio(false)#define ll long long#define INF 0x3f3f3f3ftypedef tree<pair<int,int>,null_type,less<>,rb_tree_tag,tree_order_statistics_node_update> rbtree;const int maxn = 2e5 + 10;int n,a[maxn],b[maxn];int main() {IO;cin >> n;for (int i = 0; i < n; i++) cin >> a[i];for (int i = 0; i < n; i++) cin >> b[i];ll ans = 0;rbtree s;for (int i = 0; i < n; i++) {ans += s.order_of_key({a[i] - b[i], 0});s.insert({b[i] - a[i], i});}cout << ans;return 0;}
关于pbds库的具体介绍可见：
/blog/Chanis/gnu-pbds
再附上一些rbtree操作资料：
定义一颗红黑树int 关键字类型null_type无映射(低版本g++为null_mapped_type)less<int>从小到大排序rb_tree_tag 红黑树（splay_tree_tag）tree_order_statistics_node_update结点更新插入t.insert();删除t.erase();Rank:t.order_of_key();第K值:t.find_by_order();前驱:t.lower_bound();后继t.upper_bound();a.join(b)b并入a 前提是两棵树的key的取值范围不相交a.split(v,b)key小于等于v的元素属于a，其余的属于bT.lower_bound(x) >=x的min的迭代器T.upper_bound((x) >x的min的迭代器T.find_by_order(k) 有k个数比它小的数
离线 + 树状数组，具体代码不贴了，当时用这个过的，写了很久感觉自己很傻逼。
后面两个思路，我们先要想到，因为原式可以变换为 ci > - cj,和 cj > -ci, 所以原数组的顺序并不重要，即可以排序。
所以我们将数组c递增排序，要满足ci + cj > 0，我们从两边类似尺取，如果 c[l] + c[r] > 0 那么由于数组是递增排序的我们可以知道，c[ l --> (r - 1) ] + c[r] > 0 是一定的，这样向中间逼近就能得到答案；
#include <bits/stdc++.h>using namespace std;#define IO std::ios::sync_with_stdio(false)#define int long long#define rep(i , j , n) for(int i = j ; i <= n ; i++)#define red(i , n , j) for(int i = n ; i >= j ; i--)#define INF 0x3f3f3f3fconst int maxn = 2e5 + 10;int n,a[maxn],b[maxn],c[maxn];signed main() {IO;cin >> n;rep(i,1,n) cin >> a[i];rep(i,1,n) cin >> b[i];vector<int> vec;rep(i,1,n) c[i] = a[i] - b[i];sort(c+1,c+n+1);int ans = 0;int l = 1 , r = n;while (true){if(c[l] + c[r] > 0) ans += (r - l),r--;else l++;if(l == r) break;}cout << ans << endl;return 0;}
将数组c递增排序，变形一下原式为 -ci < cj，我们对于每个ci，往后直接二分查找大于 -ci 的数有多少个就可以了；
#include <bits/stdc++.h>using namespace std;#define IO std::ios::sync_with_stdio(false)#define int long long#define rep(i , j , n) for(int i = j ; i <= n ; i++)#define red(i , n , j) for(int i = n ; i >= j ; i--)#define INF 0x3f3f3f3fconst int maxn = 2e5 + 10;int n,a[maxn],b[maxn],c[maxn];signed main() {IO;cin >> n;rep(i,1,n) cin >> a[i];rep(i,1,n) cin >> b[i];rep(i,1,n) c[i] = a[i] - b[i];sort(c+1,c+n+1);int ans = 0;rep(i,1,n){int cnt = upper_bound(c+i+1,c+n+1,-c[i]) - c;ans += n - cnt + 1;}cout << ans << endl;return 0;}
