3262: 陌上花开
Time Limit: 20 Sec Memory Limit: 256 MB Submit: 366 Solved: 163 [Submit][Status][Discuss] Description
有n朵花，每朵花有三个属性：花形(s)、颜色(c)、气味(m)，又三个整数表示。现要对每朵花评级，一朵花的级别是它拥有的美丽能超过的花的数量。定义一朵花A比另一朵花B要美丽，当且仅当Sa>=Sb,Ca>=Cb,Ma>=Mb。显然，两朵花可能有同样的属性。需要统计出评出每个等级的花的数量。 Input
第一行为N,K (1 <= N <= 100,000, 1 <= K <= 200,000 ), 分别表示花的数量和最大属性值。 以下N行，每行三个整数si, ci, mi (1 <= si, ci, mi <= K)，表示第i朵花的属性 Output
包含N行，分别表示评级为0…N-1的每级花的数量。 Sample Input
10 3
3 3 3
2 3 3
2 3 1
3 1 1
3 1 2
1 3 1
1 1 2
1 2 2
1 3 2
1 2 1
Sample Output
3
1
3
0
1
0
1
0
0
1
HINT
1 <= N <= 100,000, 1 <= K <= 200,000
这道题我是用CDQ分治（树套树也可以）来做的。
维护三维偏序: 第一维排序，第二位CDQ分治，第三维树状数组。
首先我们可以把三维都相的合并到一起，一块计算。
我们按照s排序，然后依次把他们赋值为1..tot（这里可以把s类比为id）。
接下来按照c排序，开始CDQ分治。
计算左边对右边的影响的时候: ①左边的s都小于右边 ②在每一边c也是依次递增的 ③我们只要扫描右边，把左边c小于等于当前的花的花的m加入到树状数组，统计目前树状数组中m小于等于当前扫描到的花的m的个数就是左边三维都小于等于当前花得个数。
using namespace std;int now,n,ans[M],k;struct data{int c,s,m,num,ans;}a[M],b[M],q[M];struct BIT{int v,T;}t[M*3];void read(int &tmp){tmp=0;char ch=getchar();int fu=1;for (;ch<‘0’||ch>’9′;ch=getchar())if (ch==’-‘) fu=-1;for (;ch>=’0’&&ch<=’9’;ch=getchar())tmp=tmp*10+ch-‘0’;tmp*=fu;}bool cmp(data a,data b){if (a.s==b.s&&a.c==b.c) return a.m<b.m;if (a.s==b.s) return a.c<b.c;return a.s<b.s; }bool cmp2(data a,data b){if (a.c==b.c&&a.s==b.s) return a.m<b.m;if (a.c==b.c) return a.s<b.s;return a.c<b.c;}int lowbit(int x){return x&(-x);}void Update(int x,int p){for (int i=x;i<=k;i+=lowbit(i)){if (t[i].T==now) t[i].v+=p;else t[i].T=now,t[i].v=p;}}int Getsum(int x){int ans=0;for (int i=x;i;i-=lowbit(i))if (t[i].T==now) ans+=t[i].v;return ans;}void CDQ(int l,int r){if (l==r){a[l].ans+=(a[l].num-1);return;}int m=(l+r)>>1;int q1=l,q2=m+1;for (int i=l;i<=r;i++)if (q1<=m&&a[i].s<=m)q[q1++]=a[i];else q[q2++]=a[i];for (int i=l;i<=r;i++)a[i]=q[i];CDQ(l,m);now++;int j=l;for (int i=m+1;i<=r;i++){for (;j<=m;j++)if (a[i].c>=a[j].c) Update(a[j].m,a[j].num);else break;a[i].ans+=Getsum(a[i].m);}CDQ(m+1,r);q1=l,q2=m+1;for (int i=l;i<=r;i++)if ((a[q1].c<=a[q2].c||q2>r)&&q1<=m)q[i]=a[q1++];else q[i]=a[q2++];for (int i=l;i<=r;i++)a[i]=q[i];}int main(){now=0;read(n);read(k);for (int i=1;i<=n;i++)read(a[i].s),read(a[i].c),read(a[i].m),a[i].num=1;sort(a+1,a+1+n,cmp);int tot=0;for (int i=1;i<=n;i++){int k=(a[i].s==a[i-1].s)&(a[i].c==a[i-1].c)&(a[i].m==a[i-1].m);if (i==1||!k)a[++tot]=a[i];else a[tot].num++;}for (int i=1;i<=tot;i++)a[i].s=i,a[i].ans=0;sort(a+1,a+1+tot,cmp2);CDQ(1,tot);for (int i=1;i<=tot;i++)ans[a[i].ans]+=a[i].num;for (int i=0;i<n;i++)printf(“%d\n”,ans[i]);return 0;}
其实一开始写的CDQ分治并不是这样的，我是在CDQ分治中对c排的序，把c当做类似id的东西来分出左边右边的，那么这样就会有问题了，有多个c相同的时候谁在左边谁在右边？
我用一个变量c记录左边有几个与中间值相同的，nn作为扫描时候的计数器（统计目前等于中间值的有几个了），，当计数器大于等于c之后，再碰到等于c的直接放在右边。
后来逐渐有广州花城的，
