传送门
真是一道毒瘤题（弄了接近一下午+一晚上）
解题思路
先对所有的点按照a-b-c的优先值从小到大排序，然后去重（注意要记录每一个有几个重复的，因为条件是小于等于，所以重复的对答案也有影响），然后再按照关键字b归并排序，排序过程中，用树状数组记录c值，每一次合并时如果是右半部分的b值较小，答案就加上先前的所有c值小于这个c值的个数。
由于用memset时间复杂度过大，所以进行完操作后用for循环对所有更改过的点进行修改。
然后因为答案问的不是总数，所以用一系列数组来维护各种值，及其恶心。
然后注意k值实际上就是树状数组的边界，千万不能用n，否则会wa三个点。
然后才能顺利AC。
AC代码
1 #include<iostream> 2 #include<algorithm> 3 #include<cmath> 4 #include<cstdio> 5 #include<cstring> 6 using namespace std; 7 const int maxn=100005; 8 int n,k,ans[maxn],anss[maxn],numm[maxn]; 9 struct node{ 10 int id,a,b,c,num; 11 }p[maxn],q[maxn]; 12 bool cmp(const node &x,const node &y){ 13 if(x.a!=y.a){ 14 return x.a<y.a; 15 } 16 if(x.b!=y.b){ 17 return x.b<y.b; 18 } 19 return x.c<y.c; 20 } 21 inline int lowbit(int x){ 22 return x&-x; 23 } 24 int c[2*maxn]; 25 void update(int x,int v){ 26 for(int i=x;i<=k;i+=lowbit(i)){ 27 c[i]+=v; 28 } 29 } 30 int query(int x){ 31 int res=0; 32 for(int i=x;i>0;i-=lowbit(i)){ 33 res+=c[i]; 34 } 35 return res; 36 } 37 void divide(int l,int r){ 38 if(l==r) return; 39 int mid=(l+r)>>1; 40 int p1=l,p2=mid+1,tot=0; 41 divide(l,mid); 42 divide(mid+1,r); 43 while(p1<=mid||p2<=r){ 44 if(p1<=mid&&(p2>r||p[p1].b<=p[p2].b)){ 45 q[++tot]=p[p1++]; 46 update(q[tot].c,q[tot].num); 47 }else{ 48 q[++tot]=p[p2++]; 49 ans[q[tot].id]+=query(q[tot].c); 50 } 51 } 52 for(int i=l;i<=mid;i++){ 53 update(p[i].c,-p[i].num); 54 } 55 for(int i=1;i<=tot;i++){ 56 p[l+i-1]=q[i]; 57 } 58 } 59 int main() 60 { 61 cin>>n>>k; 62 for(int i=1;i<=n;i++){ 63 scanf("%d%d%d",&p[i].a,&p[i].b,&p[i].c); 64 } 65 sort(p+1,p+n+1,cmp); 66 int tot=0; 67 for(int i=1;i<=n;){ 68 int j=i,cnt=0; 69 while(j<=n&&p[i].a==p[j].a&&p[i].b==p[j].b&&p[i].c==p[j].c){ 70 p[i].num++; 71 cnt++; 72 j++; 73 } 74 q[++tot]=p[i]; 75 numm[tot]=cnt; 76 i=j; 77 } 78 int nn=n; 79 n=tot; 80 memset(p,0,sizeof(p)); 81 for(int i=1;i<=tot;i++) p[i]=q[i],p[i].id=i; 82 divide(1,n); 83 for(int i=1;i<=n;i++){ 84 ans[i]+=numm[i]-1; 85 } 86 for(int i=1;i<=n;i++){ 87 anss[ans[i]]+=numm[i]; 88 } 89 for(int i=0;i<nn;i++) printf("%d ",anss[i]); 90 return 0; 91 }
寒假作业已经放弃了qwq