BZOJ 3262: 陌上花开

正文索引 [隐藏]

Input
Output
Sample Input
Sample Output
HINT
题解
代码

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
1
1
1

HINT

1 <= N <= 100,000, 1 <= K <= 200,000

题解

好好理解了一下CDQ分治！其实就是分治左边部分和右边部分，算整体的时候把左边对右边的影响加回去！
这道题目我们第一维使用排序，第二维用CDQ分治，第三位使用树状数组。就可以啦！
Orz3165还在填坑状态，等数据中、、、

代码

#include<cstdio>
#include<algorithm>
using namespace std;
const int Maxn=200005;
int tree[Maxn];
inline int lowbit(int x){
    return x&(-x);
}
inline void add(int x,int val){
    for (int i=x;i<=Maxn;i+=lowbit(i)) tree[i]+=val;
}
inline int get(int x){
    int sum=0;
    for (int i=x;i;i-=lowbit(i)) sum+=tree[i];
    return sum;
}
struct Flower{
    int a,b,c,s;
    int ans;
};
Flower f[100010];
int nume=0;
Flower p[100010];
bool cmp(Flower a,Flower b){
    if (a.a==b.a && a.b==b.b) return a.c<b.c;
    if (a.a==b.a) return a.b<b.b;
    return a.a<b.a;
}
bool cmpCDQ(Flower a,Flower b){
    if (a.b==b.b) return a.c<b.c;
    return a.b<b.b;
}
void solve(int left,int right){
    if (left==right) return;
    int mid=(left+right)/2;
    solve(left,mid);
    solve(mid+1,right);
    sort(p+left,p+mid+1,cmpCDQ);
    sort(p+mid+1,p+right+1,cmpCDQ);
    int i,j;
    for (j=mid+1,i=left;j<=right;j++){
        for (;p[i].b<=p[j].b && i<=mid;i++)
            add(p[i].c,p[i].s);
        p[j].ans+=get(p[j].c);
    }
    for (int k=left;k<i;k++) add(p[k].c,-p[k].s);
}
int n;
int ans[100010];
int main(){
    int tmp=0;
    scanf("%d%d",&n,&tmp);
    for (int i=1;i<=n;i++){
        scanf("%d%d%d",&f[i].a,&f[i].b,&f[i].c);
    }
    sort(f+1,f+n+1,cmp);
    int cnt=0;
    for (int i=1;i<=n;i++){
        cnt++;
        if (f[i].a!=f[i+1].a || f[i].b!=f[i+1].b || f[i].c!=f[i+1].c){
            p[++nume]=f[i];
            p[nume].s=cnt;
            p[nume].ans=0;
            cnt=0;
        }
    }
    solve(1,nume);
    for (int i=1;i<=nume;i++)
        ans[p[i].ans+p[i].s-1]+=p[i].s;
    for (int i=0;i<n;i++)
        printf("%d\n",ans[i]);
    return 0;
}

#include<cstdio>

#include<algorithm>

using namespace std;

const int Maxn=200005;

int tree[Maxn];

inline int lowbit(int x){

return x&(-x);

}

inline void add(int x,int val){

for (int i=x;i<=Maxn;i+=lowbit(i)) tree[i]+=val;

}

inline int get(int x){

int sum=0;

for (int i=x;i;i-=lowbit(i)) sum+=tree[i];

return sum;

}

struct Flower{

int a,b,c,s;

int ans;

};

Flower f[100010];

int nume=0;

Flower p[100010];

bool cmp(Flower a,Flower b){

if (a.a==b.a && a.b==b.b) return a.c<b.c;

if (a.a==b.a) return a.b<b.b;

return a.a<b.a;

}

bool cmpCDQ(Flower a,Flower b){

if (a.b==b.b) return a.c<b.c;

return a.b<b.b;

}

void solve(int left,int right){

if (left==right) return;

int mid=(left+right)/2;

solve(left,mid);

solve(mid+1,right);

sort(p+left,p+mid+1,cmpCDQ);

sort(p+mid+1,p+right+1,cmpCDQ);

int i,j;

for (j=mid+1,i=left;j<=right;j++){

for (;p[i].b<=p[j].b && i<=mid;i++)

add(p[i].c,p[i].s);

p[j].ans+=get(p[j].c);

}

for (int k=left;k<i;k++) add(p[k].c,-p[k].s);

}

int n;

int ans[100010];

int main(){

int tmp=0;

scanf("%d%d",&n,&tmp);

for (int i=1;i<=n;i++){

scanf("%d%d%d",&f[i].a,&f[i].b,&f[i].c);

}

sort(f+1,f+n+1,cmp);

int cnt=0;

for (int i=1;i<=n;i++){

cnt++;

if (f[i].a!=f[i+1].a || f[i].b!=f[i+1].b || f[i].c!=f[i+1].c){

p[++nume]=f[i];

p[nume].s=cnt;

p[nume].ans=0;

cnt=0;

}

solve(1,nume);

for (int i=1;i<=nume;i++)

ans[p[i].ans+p[i].s-1]+=p[i].s;

for (int i=0;i<n;i++)

printf("%d\n",ans[i]);

return 0;

}

一	二	三	四	五	六	日
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31

WNJXYKの博客

喂你脚下有坑