Gym - 101908C[树状数组+离散化]

降维，横纵分开考虑。多一个交点就多一块
计算有多少交点。树状数组维护一下逆序对就可以了

#include <bits/stdc++.h>
#define cl(a) memset(a,0,sizeof(a))
#define sc(x) scanf("%d",&x)
using namespace std;
typedef long long ll;
typedef pair<ll,ll>PLL;
const int maxn =  2e5+50;
// init
ll n,m,c,r;
vector<PLL> v;
vector<PLL> rv;
//bit
int lowbit(int x){return x&(-x);}
int bit[maxn];
void add(int k,int ma)
{
    while(k<=ma)
    {
        bit[k]+=1;
        k += lowbit(k);
    }
}
int sum(int k)
{
    int ans=0;
    while(k>0)
    {
        ans+=bit[k];
        k-=lowbit(k);
    }
    return ans;
}
//discretizing
vector<ll>a;
inline int getID(ll x){return lower_bound(a.begin(),a.end(),x)-a.begin()+1;}
void cle(){a.clear();cl(bit);}
ll solve1()
{
    ll s =0;
    sort(v.begin(),v.end());
    for(int i=0;i<v.size();i++)
    {
        int t = v[i].second;
        int id = getID(t);
        s += sum(getID(n))-sum(id);
      // cout<<"s= "<<s<<" "<<endl;
        add(id,getID(n));
    }
    return s;
}
ll solve2()
{
    ll s =0;
    sort(rv.begin(),rv.end());
    for(int i=0;i<rv.size();i++)
    {
        ll t = rv[i].second;
        int id = getID(t);
        s+=sum(getID(m))-sum(id);
        add(id,getID(m));
    }
    return s;
}
int main()
{
    scanf("%lld%lld%lld%lld",&n,&m,&c,&r);
    a.push_back(n);
    for(int i=1;i<=c;i++)
    {
        PLL t;
        scanf("%lld%lld",&t.first,&t.second);
        v.push_back(t);
        a.push_back(t.first);
        a.push_back(t.second);
    }
    sort(a.begin(),a.end());
    a.erase(unique(a.begin(),a.end()),a.end());
    ll ans1 = solve1();
   // cout<<ans1<<endl;
    cle();
    for(int i=1;i<=r;i++)
    {
        PLL t;
        scanf("%lld%lld",&t.first,&t.second);
        a.push_back(t.first);
        a.push_back(t.second);
        rv.push_back(t);
    }
    sort(a.begin(),a.end());
    a.erase(unique(a.begin(),a.end()),a.end());
    ll ans2 = solve2();
    ll allans = ans1+ans2+(c+1LL)*(r+1LL);
    printf("%lld\n",allans);
    return 0;
}