CDQ套CDQ或者CDQ套树套树
前者快于后者然而我写了后者# include# include # include # include # include # define IL inline# define RG register# define Fill(a, b) memset(a, b, sizeof(a))using namespace std;typedef long long ll;IL ll Read(){ RG char c = getchar(); RG ll x = 0, z = 1; for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1; for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + c - '0'; return x * z;}const int MAXN(50010);int n, k, ans, cnt;struct Point{ int a, b, c, d; IL bool operator <(RG Point B) const{ if(a != B.a) return a < B.a; if(b != B.b) return b < B.b; if(c != B.c) return c < B.c; return d < B.d; }} p[MAXN];struct Treap{ int key, fix, size, num; Treap *ch[2]; IL Treap(int x){ num = size = 1; fix = rand(); key = x; ch[0] = ch[1] = NULL; }} *root[MAXN << 1];IL void Updata(Treap *x){ x -> size = x -> num; if(x -> ch[0] != NULL) x -> size += x -> ch[0] -> size; if(x -> ch[1] != NULL) x -> size += x -> ch[1] -> size;}IL void Rot(Treap *&x, int c){ Treap *y = x -> ch[!c]; x -> ch[!c] = y -> ch[c]; y -> ch[c] = x; Updata(x); Updata(y); x = y;}IL void Insert(Treap *&x, int val){ if(x == NULL) x = new Treap(val); else if(x -> key == val) x -> num++; else{ int c = val > x -> key; Insert(x -> ch[c], val); if(x -> ch[c] -> fix > x -> fix) Rot(x, c ^ 1); } Updata(x);}IL void Delete(Treap *&x, int val){ if(val == x -> key){ Treap *tmp = x; if(x -> num > 1) x -> num--; else if(x -> ch[0] == NULL){ x = x -> ch[1]; delete tmp; } else if(x -> ch[1] == NULL){ x = x -> ch[0]; delete tmp; } else{ int c = x -> ch[0] -> fix > x -> ch[1] -> fix; Rot(x, c); Delete(x -> ch[c], val); } } else{ int c = val > x -> key; Delete(x -> ch[c], val); } if(x != NULL) Updata(x);}IL void Rank(Treap *x, int val){ if(x == NULL) return; if(val < x -> key) Rank(x -> ch[0], val); else{ if(x -> ch[0] != NULL) cnt += x -> ch[0] -> size; if(x -> key == val) return; cnt += x -> num; Rank(x -> ch[1], val); }}IL void Add(RG int x, RG int y){ for(; x <= n; x += x & -x) Insert(root[x], y); }IL int Query(RG int x, RG int y){ cnt = 0; for(; x; x -= x & -x) Rank(root[x], y); return cnt; } IL void Del(RG int x, RG int y){ for(; x <= n; x += x & -x) Delete(root[x], y); }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); sort(p + l, p + r + 1);//可以归并排序 for(RG int i = l; i <= r; i++) if(p[i].d <= mid) Add(p[i].b, p[i].c); else ans += Query(p[i].b, p[i].c); for(RG int i = l; i <= r; i++) if(p[i].d <= mid) Del(p[i].b, p[i].c);}int main(RG int argc, RG char* argv[]){ n = Read(); for(RG int i = 1; i <= n; i++) p[i].a = Read(); for(RG int i = 1; i <= n; i++) p[i].b = Read(); for(RG int i = 1; i <= n; i++) p[i].c = Read(); for(RG int i = 1; i <= n; i++) p[i].d = i; CDQ(1, n); printf("%d\n", ans); return 0;}