求卡常

#pragma GCC optimize(2,3,"Ofast","inline")

#include <bits/stdc++.h>
  
//#define int long long
#define ll long long
#define double long double
#define pii pair<int,int> 
#define fi first
#define se second
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define sz(s) ((int)s.size())
#define lowbit(x) (x&-x)
#define endl "\n"
     
using namespace std;
     
void inline solve(int C);

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    srand(time(0));
    int T=1,C=0;
    //cin >> C;
    cin >> T;
    while(T--) solve(C);
    return 0;
}

const int N=3e6+10;
int n,p,q,bst[N],dp[N],mx[N*4],tg[N*4];
ll s[N*4],ans;
vector<int> lsh,v;
pii a[N];
void inline add(int x,int k){
    while(x<=sz(lsh)){
        bst[x]=max(bst[x],k);
        x+=lowbit(x);
    }
}
int inline ask(int x){
    int res=0;
    while(x){
        res=max(res,bst[x]);
        x^=lowbit(x);
    }
    return res;
}
bool cmp(pii x,pii y){
    if(x.fi!=y.fi) return x.fi<y.fi;
    return x.se>y.se;
}
void inline pushdown(int idx,int l,int r){
    if(tg[idx]==-1) return;
    int mid=(l+r)/2;
    mx[idx*2]=mx[idx*2+1]=tg[idx];
    s[idx*2]=1ll*(lsh[mid-1]-lsh[l-1]+1)*tg[idx];
    s[idx*2+1]=1ll*(lsh[r-1]-lsh[mid-1])*tg[idx];
    tg[idx*2]=tg[idx*2+1]=tg[idx];
    tg[idx]=-1;
}
void inline pushup(int idx){
    mx[idx]=max(mx[idx*2],mx[idx*2+1]);
    s[idx]=s[idx*2]+s[idx*2+1];
}
void inline modify(int fl,int fr,int val,int l=1,int r=sz(lsh),int idx=1){
    if(fl==l && fr==r){
        s[idx]=1ll*(lsh[r-1]-lsh[l-1]+1)*val;
        mx[idx]=val;
        tg[idx]=val;
        return;
    }
    int mid=(l+r)/2;
    pushdown(idx,l,r);
    if(fr<=mid) modify(fl,fr,val,l,mid,idx*2);
    else if(fl>mid) modify(fl,fr,val,mid+1,r,idx*2+1);
    else modify(fl,mid,val,l,mid,idx*2),modify(mid+1,fr,val,mid+1,r,idx*2+1);
    pushup(idx);
}
int inline query(int val,int l=1,int r=sz(lsh),int idx=1){
    if(mx[idx]<val) return r; 
    if(l==r) return l;
    int mid=(l+r)/2;
    pushdown(idx,l,r);
    if(mx[idx*2]<=val) return query(val,l,mid,idx*2);
    return query(val,mid+1,r,idx*2+1);
}
ll inline ASK(int fl,int fr,int l=1,int r=sz(lsh),int idx=1){
    if(fl==l && fr==r) return s[idx];
    int mid=(l+r)/2;
    pushdown(idx,l,r);
    if(fr<=mid) return ASK(fl,fr,l,mid,idx*2);
    else if(fl>mid) return ASK(fl,fr,mid+1,r,idx*2+1);
    return ASK(fl,mid,l,mid,idx*2)+ASK(mid+1,fr,mid+1,r,idx*2+1);
}

void inline solve(int C){
    lsh.clear();
    cin >> n >> p >> q;
    for(int i=1;i<=n;i++){
        cin >> a[i].fi >> a[i].se;
        v.pb(a[i].fi-1),v.pb(a[i].fi),v.pb(a[i].fi+1);
        lsh.pb(max(a[i].se-1,0)),lsh.pb(a[i].se),lsh.pb(a[i].se+1);
    }
    v.pb(0),lsh.pb(0),v.pb(p),v.pb(p-1),v.pb(p+1),lsh.pb(q),lsh.pb(q-1),lsh.pb(q+1);
    sort(lsh.begin(),lsh.end());
    lsh.resize(unique(lsh.begin(),lsh.end())-lsh.begin());
    sort(v.begin(),v.end());
    v.resize(unique(v.begin(),v.end())-v.begin());
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=sz(lsh);i++) bst[i]=0;
    for(int i=1;i<=4*sz(lsh);i++) s[i]=mx[i]=0,tg[i]=-1;
    for(int i=1;i<=n;i++){
        int x=lower_bound(lsh.begin(),lsh.end(),a[i].se)-lsh.begin()+1;
        dp[i]=ask(x)+1;
        add(x,1);
    }
    ans=1ll*(p+1)*p/2*(q+1)+1ll*(q+1)*q/2*(p+1);
    int L=lower_bound(lsh.begin(),lsh.end(),0)-lsh.begin()+1;
    int R=lower_bound(lsh.begin(),lsh.end(),q)-lsh.begin()+1;
    for(int i=0,j=1;i<sz(v)-1;i++){
        while(j<=n && a[j].fi+1==v[i]){
            int x=lower_bound(lsh.begin(),lsh.end(),a[j].se+1)-lsh.begin()+1;
            int y=query(dp[j]);
            if(x<=y) modify(x,y,dp[j]);
            j++;
        }
        if(v[i]<=p && v[i]>=0) ans-=1ll*(v[i+1]-v[i])*ASK(L,R);
    }
    cout << ans << endl;
}