陌上花開（三維偏序）

模闆題：

三維偏序。

一維CDQ一維離線排序解決一維樹狀數組。

細節問題。這個題的偏序可以相等就很惡心。

注意離線排序和CDQ還有樹狀數組都不能完美的解決有相等元素互相貢獻的問題，隻會由小标号貢獻到大标号（視實作方式而定），這個可以事後用一個 m a p map map把相等的貢獻加回去。但是不相等，因為是一層層剝開的偏序，是以在外層相等時，一定要讓内層小的放外面。

A C   C o d e AC\ Code AC Code

#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define maxn 100005
using namespace std;

int n,K;
int x[maxn],y[maxn],z[maxn],c[maxn],a[maxn],cnt[maxn],ans[maxn],tr[maxn*2],c2[maxn];
map<tuple<int,int,int>,int>mp;
inline bool cmp(const int &u,const int &v){
	return z[u] == z[v] ? x[u] == x[v] ? y[u] == y[v] ? u<v : y[u] < y[v] : x[u] < x[v] : z[u] < z[v];
}
inline void upd(int u,int v){ for(;u<=K;u+=u&-u) tr[u]+=v; }
inline int qsum(int u){ int ret=0;for(;u;u-=u&-u) ret+=tr[u];return ret; }
void Solve(int l,int r){
	if(l>=r) return;
	int mid = (l+r) >> 1;
	Solve(l,mid),Solve(mid+1,r);
	for(int i=l,j=mid+1,k=l;(i<=mid || j<=r);){
		if(j>r || (i<=mid && x[c[i]]<=x[c[j]])){
			upd(y[c[i]],1);
			a[k++] = c[i++];
		}
		else{
			ans[c[j]]+=qsum(y[c[j]]);
			a[k++] = c[j++];
		}		
	}
	for(int i=l;i<=mid;i++) upd(y[c[i]],-1);	
	for(int i=l;i<=r;i++) c[i] = a[i];
}

int main(){
	scanf("%d%d",&n,&K);
	for(int i=1;i<=n;i++)
		scanf("%d%d%d",&x[i],&y[i],&z[i]),c[i]=i;
	for(int i=n;i>=1;i--)
		ans[i] += mp[make_tuple(x[i],y[i],z[i])]++;
	sort(c+1,c+1+n,cmp);
	Solve(1,n);
	for(int i=1;i<=n;i++) cnt[ans[i]]++;
	for(int i=0;i<n;i++) printf("%d\n",cnt[i]);
}
           

UPD:

樹狀數組套樹狀數組解法：

A C   C o d e \mathcal AC \ Code AC Code

#include<bits/stdc++.h>
#define maxn 200005
#define rep(i,j,k) for(int i=(j),LIM=(k);i<=LIM;i++)
#define pb push_back
#define mp make_pair
using namespace std;

int n,K;
struct node{ int a,b,c; bool operator <(const node &B)const{ return a == B.a ? b == B.b ? c < B.c : b < B.b : a < B.a; }}A[maxn];
int tr[maxn],vis[maxn],ans[maxn],f[maxn],g[maxn],tim;
void upd(int u,int v){ for(;u<maxn;u+=u&-u) (vis[u] != tim) && (vis[u] = tim , tr[u] = 0) , tr[u] += v; }
int qry(int u){ int r=0;for(;u;u-=u&-u) if(vis[u] == tim) r += tr[u]; return r; }
vector<pair<int,int> >Q[maxn];

int main(){
	scanf("%d%d",&n,&K);
	rep(i,1,n) scanf("%d%d%d",&A[i].a,&A[i].b,&A[i].c);
	sort(A+1,A+1+n);
	rep(i,1,n){
		for(int u=A[i].b;u;u-=u&-u) Q[u].pb(mp(i,0));
		for(int u=A[i].b;u<maxn;u+=u&-u) Q[u].pb(mp(A[i].c,1));
	}
	for(tim=1;tim<maxn;tim++) for(auto u:Q[tim])
		if(u.second == 0) f[u.first] += qry(A[u.first].c);
		else upd(u.first,1);
	for(int i=n;i>=1;i--) g[i] = (A[i].a == A[i+1].a && A[i].b == A[i+1].b && A[i].c == A[i+1].c) ? g[i+1] + 1 : 1 , f[i] += g[i] - 1;
	rep(i,1,n) ans[f[i]] ++;
	rep(i,0,n-1) printf("%d\n",ans[i]);
}