CF1569D Inconvenient Pairs

知识点：数据结构、分组、双指针、二分、STL、思维

题目链接

题意

$10^6\times 10^6$的整点网格的网格线上分布n条竖直线和m条横直线（不重叠），直线上分布k个整点，求两点沿已知直线行走的最短路径长度不等于两点的Manhattan距离组成的对数（无序）。

思路

参考awoo的CF官方题解。
在两直线之间记为行或列，两点不在同行同列的情况下两种情况均不满足题意：
1、两点都在各自的横/竖线，必能经过两点之间夹的一条竖/横线达到Manhattan距离。
2、一点在横线，一点在竖线，经过两点所在直线的交点的路径达到Manhattan距离。
此外，同一线上的点不满足题意；即同行同列的不在同一线上的两点满足题意。
对同行同列的点分组，每组点再按在同一直线上的点分组，按行排序组，枚举组，答案每次加上该组点数量乘以之前点数量。
实现思路见代码。

代码

#include"bits/stdc++.h"
#define ll long long
#define db(x) cout<<fixed<<setprecision(14)<<#x<<':'<<(x)<<endl
#define pb push_back
#define x first
#define y second
#define max(a,b) (a<b?b:a)
#define mix(a,b) (a<b?a:b)
#define vec vector<ll>
#define mid (l+r>>1)
#define sl rt<<1,l,mid
#define sr rt<<1|1,mid+1,r
#define tdata 1,1,n
#define tinfo ll rt,ll l,ll r
#define all(a) (a).begin(),(a).end()
using namespace std;
const ll N=2e5+10,M=3e5+10,inf=1e18,mod=1e9+7;

ll t;
vec roadx,roady;//竖线横坐标，横线纵坐标
vector<pair<ll,ll> > pnt[2];//pnt[0]在同一**竖线**上的点，pnt[1]…横线…

void init(ll n,ll m) {
   
  roadx.resize(n);
  roady.resize(m);
  pnt[0].resize(0);
  pnt[1].resize(0);
}

int main() {
   
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin>>t;
  while(t--) {
   
    ll n,m,k;
    cin>>n>>m>>k;
    init(n,m);
    for(ll i=0; i<n; ++i) cin>>roadx[i];
    for(ll i=0; i<m; ++i) cin>>roady[i];
    for(ll i=0; i<k; ++i) {
   
      ll x,y;
      cin>>x>>y;
      //在横线或竖线上的点分组，类离散化给定点横纵坐标的组号，组号按照行/列递增，后面代码注释组号记为x，y
      ll lx=upper_bound(all(roadx),x)-roadx.begin()-1;//ex. 2.7->2
      ll ly=upper_bound(all(roady),y)-roady.begin()-1;
      if(x==roadx[lx]&&y==roady[ly]) continue;//忽略十字线上的点
      if(x==roadx[lx])
        pnt[0].pb({
   roadx[lx],roady[ly]});
      else pnt[1].pb({
   roady[ly],roadx[lx]});//与后面代码的交换算法对应
    }
    ll ans=0;
    //处理竖线，处理横线
    for(ll i=0; i<2; ++i) {
   
      auto &group=pnt[i];//取别名
      sort(all(group),[](pair<ll,ll> a,pair<ll,ll> b) {
   
        return a.y==b.y?a.x<b.x:a.y<b.y;
      });//y第一关键字，x第二关键字排序（枚举顺序）
      //同行同***定区间分组
      ll l=0,r=0;
      while(r<group.size()) {
   
        r=upper_bound(group.begin()+l,group.end(),group[l],[](pair<ll,ll> a,pair<ll,ll> b) {
   
          return a.y<b.y;
        })-group.begin();//二分y，找到区间内y相等的右端点
        //同一直线上的点确定区间分组
        ll p=l,q=l;
        //之前点的数量
        ll cnt=0;
        while(q<r) {
   
          q=upper_bound(group.begin()+p,group.begin()+r,group[p],[](pair<ll,ll> a,pair<ll,ll> b) {
   
            return a.x<b.x;
          })-group.begin();//二分x，找到区间内x相等的右端点
          ans+=cnt*(q-p);//之前点数量乘以该组点数量
          cnt+=q-p;//更新
          p=q;//移动双指针
        }
        l=r;//移动双指针
      }
      //在行上的点转化为在列上的点，相当于翻转坐标系，重复以上算法
      if(i==0) {
   
        swap(n,m);
        swap(roadx,roady);
      }
    }
    cout<<ans<<endl;
  }
  return 0;
}