Time Limit: 3000 ms Memory Limit: 256 MB
Description
有n朵花，每朵花有三个属性：花形(s)、颜色(c)、气味(m)，用三个整数表示。
现要对每朵花评级，一朵花的级别是它拥有的美丽能超过的花的数量。
定义一朵花A比另一朵花B要美丽，当且仅当 $S_a \ge S_b, C_a \ge C_b, M_a \ge M_b$。
显然，两朵花可能有同样的属性。需要统计出评出每个等级的花的数量。
Input
第一行为 N,K 分别表示花的数量和最大属性值。
以下 N 行，每行三个整数 $s_i , c_i , m_i$ 表示第i朵花的属性。
Output
包含 $N$ 行，分别表示评级为 $0…N−1$ 的每级花的数量。
Sample Input |
Sample Output |
10 3 |
3 |
题解
题目大意为，给定n个三元组，每个三元组的等级为小于等于它的三元组的个数。
其中“小于”定义为：对于两个三元组$A(s1,c1,m1)$与$B(s2,c2,m2)$，$A \le B$当且仅当$s_1 \le s_2$且$c_1 \le c_2$
且$m_1 \le b_2$。
隐隐约约想到单调性的问题。
1. 对于$s$，我们直接排序处理（按照$s$第一，$c$第二，$m$第三的优先级排序）；
2. 对于$c$，开始使用CDQ分治瞎搞（其中每次回溯的时候分别对左右区间，以$c$为第一关键字排序，为计算左区间对右区间的贡献作准备）；
3. 对于$m$：我们在CDQ分治时，已经确定左半边区间的$s$是小于右半边区间的；这时采用双指针扫描，以右区间指针指向的三元组为基准三元组。考虑此时 $c$ 是递增的，我们就将左区间的指针移到最靠右的三元组，使得这个三元组的$c$值不超过基准三元组的$c$值；
其中，我们一边扫描左区间一边将左区间扫过的三元组的$m$值丢进树状数组里，左指针到基准时，直接询问树状数组内小于等于与基准三元组的$m$值。
完全相同的几朵花怎么办？ 我们按照上面提到的排序方法排序所有花，对于相同的花，将它们的等级都标记为相同花的中等级最高的即可。
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=1e5+,K=2e5+;
int n,k,ans[N];
struct Flower{int s,c,m,sum;}f[N];
struct Bit{
int arr[K],lis[N],cnt;
void reset(){
for(;cnt;cnt--) add(lis[cnt],-,);
}
void add(int u,int num,int flag){
if(!u) return;
if(!flag)
lis[++cnt]=u;
for(;u<=k;u+=u&-u) arr[u]+=num;
}
int que(int u){
int ret=;
for(;u;u-=u&-u) ret+=arr[u];
return ret;
}
}bit;
bool cmpAll(Flower x,Flower y){
if(x.s!=y.s) return x.s<y.s;
if(x.c!=y.c) return x.c<y.c;
return x.m<y.m;
}
bool cmpC(Flower x,Flower y){return x.c<y.c;}
void cdq(int l,int r){
if(l==r) return;
int mid=(l+r)/;
cdq(l,mid);
cdq(mid+,r);
sort(f+l,f+mid+,cmpC);
sort(f+mid+,f+r+,cmpC);
int i=l,j;
bit.reset();
for(i=l,j=mid+;j<=r;j++){
while(i<=mid&&f[i].c<=f[j].c){
bit.add(f[i].m,,);
i++;
}
f[j].sum+=bit.que(f[j].m);
}
}
int main(){
scanf("%d%d",&n,&k);
for(int i=;i<=n;i++)
scanf("%d%d%d",&f[i].s,&f[i].c,&f[i].m);
sort(f+,f++n,cmpAll);
cdq(,n);
sort(f+,f++n,cmpAll);
for(int i=;i<=n;){
int j=i,maxs=;
while(f[i].s==f[j].s&&f[i].c==f[j].c&&f[i].m==f[j].m){
maxs=max(maxs,f[j].sum);
j++;
}
ans[maxs]+=j-i;
i=j;
}
for(int i=;i<=n-;i++)
printf("%d\n",ans[i]);
return ;
}
神奇代码