三维偏序[cdq分治学习笔记]

就是让第一维有序然后归并+树状数组求两维
cdq+cdq不会告辞
#include <bits/stdc++.h>

// #define int long long

#define rep(a , b , c) for(int a = b ; a <= c ; ++ a)

#define Rep(a , b , c) for(int a = b ; a >= c ; -- a)

#define go(u) for(int i = G.head[u] , v = G.to[i] , w = G.dis[i] ; i ; v = G.to[i = G.nxt[i]] , w = G.dis[i])

using namespace std ;

using ll = long long ;

using pii = pair < int , int > ;

using vi = vector < int > ;

int read() {

  int x = 0 ; bool f = 1 ; char c = getchar() ;

  while(c < 48 || c > 57) { if(c == '-') f = 0 ; c = getchar() ; }

  while(c > 47 && c < 58) { x = (x << 1) + (x << 3) + (c & 15) ; c = getchar() ; }

  return f ? x : -x ;

}

template <class T> void print(T x , char c = '\n') {

  static char st[100] ; int stp = 0 ;

  if(! x) { putchar('0') ; }

  if(x < 0) { x = -x ; putchar('-') ; }

  while(x) { st[++ stp] = x % 10 ^ 48 ; x /= 10 ; }

  while(stp) { putchar(st[stp --]) ; } putchar(c) ;

}

template <class T> void cmax(T & x , T y) { x < y ? x = y : 0 ; }

template <class T> void cmin(T & x , T y) { x > y ? x = y : 0 ; }

const int _N = 1e6 + 10 ;

struct Group {

  int head[_N] , nxt[_N << 1] , to[_N] , dis[_N] , cnt = 1 ;

  Group () { memset(head , 0 , sizeof(head)) ; }

  void add(int u , int v , int w = 1) { nxt[++ cnt] = head[u] ; to[cnt] = v ; dis[cnt] = w ; head[u] = cnt ; }

} ;

const int N = 1e5 + 10  ;

typedef int arr[N] ;

int n , k ;

struct Node {

	int x , y , z , ans , cnt ;

	Node() {}

	bool operator < (const Node & other) const {

		if(x != other.x) return x < other.x ;

		if(y != other.y) return y < other.y ;

		return z < other.z ;

	}

	bool operator == (const Node & other) const {

		return (x == other.x) && (y == other.y) && (z == other.z) ;

	}

} a[N] , b[N] , tmp[N] ;

struct BIT {

	int c[N << 1] , mxk ;

	int low(int x) {

		return x & - x ;

	}

	void add(int x , int y) {

		if(! x) return ;

		for( ; x <= mxk ; x += low(x)) c[x] += y ;

	}

	int query(int x) {

		int ans = 0 ;

		for( ; x ; x ^= low(x)) ans += c[x] ;

		return ans ;

	}

} t ;

bool cmp(Node x , Node y) {

	if(x.y != y.y) return x.y < y.y ;

	if(x.z != y.z) return x.z < y.z ;

}

void solve(int l , int r){

//	printf("%d -> %d\n" , l , r) ;

	if(l == r) return ;

	int mid = l + r >> 1 ;

	solve(l , mid) ; solve(mid + 1 , r) ;

	int p = l ; rep(i , mid + 1 , r) {

		for( ; b[p].y <= b[i].y && p <= mid ; ++ p) t.add(b[p].z , b[p].cnt) ;

		b[i].ans += t.query(b[i].z) ;

	}

	rep(i , l , p - 1) t.add(b[i].z , -b[i].cnt) ;

	merge(b + l , b + mid + 1 , b + mid + 1 , b + r + 1 , tmp , cmp) ;

	rep(i , l , r) b[i] = tmp[i - l] ;

//	printf("%d -> %d\n" , l , r) ;

}

int ans[N] ;

signed main() {

	n = read() ; t.mxk = k = read() ;

	rep(i , 1 , n) { a[i].x = read() ; a[i].y = read() ; a[i].z = read() ; }

	sort(a + 1 , a + n + 1) ; rep(i , 1 , n) b[i] = a[i] ;

	int len = unique(b + 1 , b + n + 1) - b - 1 ; int tp = 1 ;

	rep(i , 1 , n) if(a[i] == b[tp]) ++ b[tp].cnt ; else ++ b[++ tp].cnt ;

	solve(1 , len) ;

	rep(i , 1 , len) { ans[b[i].ans + b[i].cnt - 1] += b[i].cnt ; }

	rep(i , 0 , n - 1) print(ans[i]) ;

	return 0 ;

}
先咕着
秒客网

三维偏序[cdq分治学习笔记]

相关文章
