经典的三位偏序经(mo)典(ban)题，
一维排序，二维CDQ分治，3维BIT
Code
#include <cstdio>
#include <algorithm>
#define lowbit(x) ((x)&(-x))
#define N 100010
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
struct flower{
int a,b,c,w,s;
flower(){a=b=c=w=s=0;}
friend bool operator <(flower x,flower y){
return (x.a==y.a&&x.b==y.b)?(x.c<y.c):((x.a==y.a)?x.b<y.b:x.a<y.a);
}
friend bool operator ==(flower x,flower y){
return (x.a==y.a&&x.b==y.b&&x.c==y.c);
}
void rd(){a=read(),b=read(),c=read(),w=1;}
}A[N],tmp[N];
int n,mx,na,T[N*2],Ans[N];
inline void Init(){
n=read(),mx=read();
for(int i=1;i<=n;A[i++].rd());
sort(A+1,A+n+1);
int p=1;
for(int i=2;i<=n;++i) if(A[i]==A[p]) A[p].w++;else A[++p]=A[i];//去重
na=n,n=p;
}
void add(int x,int v){for(;x<=mx;x+=lowbit(x)) T[x]+=v;}
int sum(int x){int r=0;for(;x;x-=lowbit(x)) r+=T[x];return r;}
inline void solve(int l,int r){
if(l==r) return;
int m=(l+r)>>1;
solve(l,m),solve(m+1,r);
int p=l,q=m+1,cnt=l;
while(p<=m||q<=r)
if(q>r||(p<=m&&A[p].b<=A[q].b)) add(A[p].c,A[p].w),tmp[cnt++]=A[p++];
else A[q].s+=sum(A[q].c),tmp[cnt++]=A[q++];
for(int i=l;i<=m;++i) add(A[i].c,-A[i].w);//清空BIT
for(int i=l;i<=r;++i) A[i]=tmp[i];
}
int main(){
Init();
solve(1,n);
for(int i=1;i<=n;++i) Ans[A[i].s+A[i].w-1]+=A[i].w;
for(int i=0;i<na;printf("%d\n",Ans[i++]));
return 0;
}
G
M
T
| 检测语言世界语中文简体中文繁体丹麦语乌克兰语乌兹别克语乌尔都语亚美尼亚语伊博语俄语保加利亚语僧伽罗语克罗地亚语冰岛语加利西亚语加泰罗尼亚语匈牙利语南非祖鲁语卡纳达语印地语印尼巽他语印尼爪哇语印尼语古吉拉特语哈萨克语土耳其语塔吉克语塞尔维亚语塞索托语威尔士语孟加拉语宿务语尼泊尔语巴斯克语布尔语(南非荷兰语)希伯来语希腊语德语意大利语意第绪语拉丁语拉脱维亚语挪威语捷克语斯洛伐克语斯洛文尼亚语斯瓦希里语旁遮普语日语格鲁吉亚语毛利语法语波兰语波斯尼亚语波斯语泰卢固语泰米尔语泰语海地克里奥尔语爱尔兰语爱沙尼亚语瑞典语白俄罗斯语立陶宛语索马里语约鲁巴语缅甸语罗马尼亚语老挝语芬兰语苗语英语荷兰语菲律宾语葡萄牙语蒙古语西班牙语豪萨语越南语阿塞拜疆语阿尔巴尼亚语阿拉伯语韩语马其顿语马尔加什语马拉地语马拉雅拉姆语马来语马耳他语高棉语齐切瓦语 | 世界语中文简体中文繁体丹麦语乌克兰语乌兹别克语乌尔都语亚美尼亚语伊博语俄语保加利亚语僧伽罗语克罗地亚语冰岛语加利西亚语加泰罗尼亚语匈牙利语南非祖鲁语卡纳达语印地语印尼巽他语印尼爪哇语印尼语古吉拉特语哈萨克语土耳其语塔吉克语塞尔维亚语塞索托语威尔士语孟加拉语宿务语尼泊尔语巴斯克语布尔语(南非荷兰语)希伯来语希腊语德语意大利语意第绪语拉丁语拉脱维亚语挪威语捷克语斯洛伐克语斯洛文尼亚语斯瓦希里语旁遮普语日语格鲁吉亚语毛利语法语波兰语波斯尼亚语波斯语泰卢固语泰米尔语泰语海地克里奥尔语爱尔兰语爱沙尼亚语瑞典语白俄罗斯语立陶宛语索马里语约鲁巴语缅甸语罗马尼亚语老挝语芬兰语苗语英语荷兰语菲律宾语葡萄牙语蒙古语西班牙语豪萨语越南语阿塞拜疆语阿尔巴尼亚语阿拉伯语韩语马其顿语马尔加什语马拉地语马拉雅拉姆语马来语马耳他语高棉语齐切瓦语 |
文本转语音功能仅限200个字符