【CF1569】D. Inconvenient Pairs（思维+二分）

题目链接：https://codeforces.com/contest/1569/problem/D

分析

横线和竖线分开来考虑，可以发现不方便的点对只会出现在相邻两条直线之间（不包含线上的点），那么我们只需要知道相邻两条直线之间有多少点就行了，注意要减去选同一直线上点的情况。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define pb push_back
#define MP make_pairconst int inf = 1e9 + 10;
const int N = 1e6 + 10;
const ll P = 998244353;int n,m,k;
int col[N],row[N];
vector<int> a[N], b[N];
ll sum[N];int main()
{
    int T = 1;scanf("%d",&T);while(T--){
    ll ans = 0;scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=n;i++) scanf("%d",&col[i]), a[col[i]].clear();for(int i=1;i<=m;i++) scanf("%d",&row[i]), b[row[i]].clear();for(int i=1;i<=k;i++){
    int x,y;scanf("%d%d",&x,&y);a[x].pb(y);b[y].pb(x);}for(int i=1;i<=n;i++) sort(a[col[i]].begin(), a[col[i]].end());for(int i=1;i<=m;i++) sort(b[row[i]].begin(), b[row[i]].end());int now = 0, cnt = 0;ll tmp = 0;col[0] = -1, col[n + 1] = inf;for(int i=1;i<=m;i++){
    int r = row[i];cnt = 0;now = 0;tmp = 0;while(cnt < b[r].size()){
    if(b[r][cnt] >= col[now + 1]){
    sum[col[now]] += tmp, ans -= tmp * (tmp - 1) / 2;tmp = 0;int pos = upper_bound(col, col + 2 + n, b[r][cnt]) - col;now = pos - 1;}if(b[r][cnt] > col[now]) tmp++;cnt++;}sum[col[now]] += tmp, ans -= tmp * (tmp - 1) / 2;}for(int i=0;i<=n;i++) ans += sum[col[i]] * (sum[col[i]] - 1) / 2, sum[col[i]] = 0;row[0] = -1, row[m + 1] = inf;for(int i=1;i<=n;i++){
    int r = col[i];cnt = 0;now = 0;tmp = 0;while(cnt < a[r].size()){
    if(a[r][cnt] >= row[now + 1]){
    sum[row[now]] += tmp, ans -= tmp * (tmp - 1) / 2;tmp = 0;int pos = upper_bound(row, row + 2 + m, a[r][cnt]) - row;now = pos - 1;}if(a[r][cnt] > row[now]) tmp++;cnt++;}sum[row[now]] += tmp, ans -= tmp * (tmp - 1) / 2;}for(int i=0;i<=m;i++) ans += sum[row[i]] * (sum[row[i]] - 1) / 2, sum[row[i]] = 0;cout<<ans<<endl;}return 0;
}