第一维排序，第二维cdq，第三维树状数组。
干脆直接把每个点的答案都算出来，然后扫一遍，好了。
cdq果然讲起来容易写起来难，这里细讲一下代码思路。
准备工作：
①一个结构体，存入a、b、c、d（编号）。（废话）
②一个树状数组，记录c值出现的个数。
按a排序后进行递归。
先将[l，mid]、[mid+1,r]分别按b排序。
然后两边各一个指针，从小到大指，指到左边就add，指到右边就query
最后还要把左边所有的值从树状数组里删出去。
除了这道题外，还有一种板子，说的是取出最长的符合题意的序列，那要注意以下几点。
①先维护[l,mid]，再做[l,mid]对[mid+1,r]的影响，再做[mid+1,r]
②树状数组记录前缀答案最大值
③树状数组还是要随时清空
④不能直接放在一个数组里排序。每次排序是需要全部拿出来排。
真不知道自己再这上面搞那么久有没有意义。
代码：
#include<cstdio> #include<cstring> #include<iostream> #include<vector> #include<algorithm> #include<set> using namespace std; #define rep(i,j,k) for(i=j;i<=k;++i) #define per(i,j,k) for(i=j;i>=k;--i) #define LL long long #define pll pair<LL,LL> #define mkp make_pair #define X first #define Y second struct node{int a1,a2,a3,wz;}a[100005]; int n,nn,k,val[100005],ans[100005],c[200005],cnt[100005]; bool operator !=(node x,node y){ return x.a1!=y.a1||x.a2!=y.a2||x.a3!=y.a3; } bool cmp1(node x,node y){ if(x.a1!=y.a1)return x.a1<y.a1; if(x.a2!=y.a2)return x.a2<y.a2; return x.a3<y.a3; } bool cmp2(node x,node y){ return x.a2==y.a2?x.a3<y.a3:x.a2<y.a2; } void add(int x,int y){ for(;x<=k;x+=x&-x)c[x]+=y; } int query(int x){ int y=0; for(;x;x-=x&-x)y+=c[x]; return y; } void cdq(int l,int r){ if(l==r)return; int mid=l+r>>1; int i=l,j=mid+1; cdq(i,mid);cdq(j,r); sort(a+i,a+mid+1,cmp2);sort(a+j,a+r+1,cmp2); while(j<=r){ if(i<=mid&&a[i].a2<=a[j].a2) add(a[i++].a3,val[a[i].wz]); else ans[a[j++].wz]+=query(a[j].a3); } while(--i>=l) add(a[i].a3,-val[a[i].wz]); } int main(){ // freopen("r.in","r",stdin); // freopen("w.out","w",stdout); int i; scanf("%d%d",&nn,&k); rep(i,1,nn){ scanf("%d%d%d",&a[i].a1,&a[i].a2,&a[i].a3); } sort(a+1,a+nn+1,cmp1); rep(i,1,nn){ if(a[n]!=a[i])a[++n]=a[i]; ++val[n]; } rep(i,1,n)a[i].wz=i; cdq(1,n); rep(i,1,n)ans[i]+=val[i]-1; rep(i,1,n)cnt[ans[i]]+=val[i]; rep(i,0,nn-1)printf("%d\n",cnt[i]); return 0; } 其实写完发现思路并不难，但是 这题讲的是小于等于，所以细节比较多，搞了老久。