1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
using ar=array<int,2>;
using A=array<ar,2>;
bool operator<(const ar&a,const ar &b) {
return a[0]<b[0]&&a[1]<b[1];
}
bool operator<=(const ar&a,const ar &b) {
return a[0]<=b[0]&&a[1]<=b[1];
}
ar min(const ar&a,const ar &b) {return {min(a[0],b[0]),min(a[1],b[1])};}
ar max(const ar&a,const ar &b) {return {max(a[0],b[0]),max(a[1],b[1])};}
struct node {
int sum;A id;
const array<int,2> &operator[](int x)const{return id[x];}
array<int,2> &operator[](int x){return id[x];}
node operator+(const node &b)const{
return {sum+b.sum,{min(id[0],b.id[0]),max(id[1],b.id[1])}};
}
};
#define up(d) void(c[d]=c[l(d)]+c[r(d)])
void bd(int o,int L,int R,int &d) {
!d&&(d=++snt);if(L==R) return void(c[d]=a[L]);
nth_element(a+L,a+mid+1,a+R+1,[&](const A &a,const A &b){return a[0][o]<b[0][o];});
bd(!o,L,mid,l(d));bd(!o,mid+1,R,r(d));up(d);
}
node que(const A &w,int d) {
if(w[0]<=c[d][0]&&c[d][1]<=w[1]) return c[d];
if(w[1]<c[d][0]||c[d][1]<w[0]) return 0;
return que(w,l(d))+que(w,r(d));
}
|
