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
| namespace CDQ{
struct Edge{
int a,b,c,cnt,val;
bool operator < (const Edge &oth) const{
return a<oth.a || (a==oth.a && b<oth.b) || (a==oth.a && b==oth.b && c<oth.c);
}
bool operator == (const Edge &oth) const{
return a==oth.a && b==oth.b && c==oth.c;
}
}edge[MAXN],te[MAXN];
bool cmp(Edge v1, Edge v2){return v1.b<v2.b || (v1.b==v2.b && v1.c<v2.c);}
inline void cdq(int l, int r){
if (l==r) return;
int mid = (l+r)>>1;
cdq(l,mid); cdq(mid+1,r);
sort(edge+l,edge+1+mid,cmp);
sort(edge+1+mid,edge+r+1,cmp);
int L = l;
for (int R=mid+1;R<=r;R++){
while(edge[L].b<=edge[R].b && L<=mid) update(edge[L].val,edge[L].c),L++;
edge[R].cnt+=query(edge[R].c);
}
For(i,l,L-1) update(-edge[i].val,edge[i].c);
}
}
|
