题面
Sol
\(CDQ\)分治
先对\(x\)排序，对\(y\)在\(CDQ\)分治是从大到小排序
从大到小加入，右边用单调栈维护\(x\)递增，\(y\)递减的序列
左边就是找到\(x\)比它大，最小的\(y\)（树状数组解决）
再在右边找到最后一个小于这个\(y\)的位置，那么栈顶到这个位置都是答案
# include <bits/stdc++.h>
# define RG register
# define IL inline
# define Fill(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll;
const int _(2e5 + 5);
IL ll Input(){
RG ll x = 0, z = 1; RG char c = getchar();
for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;
for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
return x * z;
}
int n, bit[_];
ll ans;
struct Data{
int x, y, id;
IL bool operator <(RG Data B) const{
return x < B.x;
}
} q[_], p[_], S[_];
IL void Modify(RG int x, RG int d){
for(; x <= n; x += x & -x) bit[x] = min(bit[x], d);
}
IL void Clear(RG int x){
for(; x <= n; x += x & -x) bit[x] = bit[0];
}
IL int Query(RG int x){
RG int ret = bit[0];
for(; x; x -= x & -x) ret = min(ret, bit[x]);
return ret;
}
IL void CDQ(RG int l, RG int r){
if(l == r) return;
RG int mid = (l + r) >> 1;
CDQ(l, mid); CDQ(mid + 1, r);
for(RG int i = l, j = mid + 1, k = l; k <= r; ++k)
if(j > r || (i <= mid && p[i].y > p[j].y)) q[k] = p[i++];
else q[k] = p[j++];
for(RG int i = l; i <= r; ++i) p[i] = q[i];
RG int top = 0;
for(RG int i = l; i <= r; ++i)
if(p[i].id <= mid){
RG int v = Query(n - p[i].id + 1);
Modify(n - p[i].id + 1, p[i].y);
RG int ll = 1, rr = top, cnt = 0;
while(ll <= rr){
RG int mmid = (ll + rr) >> 1;
if(S[mmid].y < v) cnt = mmid, rr = mmid - 1;
else ll = mmid + 1;
}
if(cnt) ans += top - cnt + 1;
}
else{
while(top && S[top].x > p[i].x) --top;
S[++top] = p[i];
}
for(RG int i = l; i <= r; ++i)
if(p[i].id <= mid) Clear(n - p[i].id + 1);
}
int main(RG int argc, RG char* argv[]){
n = Input(); Fill(bit, 127);
for(RG int i = 1; i <= n; ++i) p[i].x = Input(), p[i].y = Input();
sort(p + 1, p + n + 1);
for(RG int i = 1; i <= n; ++i) p[i].id = i;
CDQ(1, n);
printf("%lld\n", ans);
return 0;
}