[BZOJ 3262] 陌上花开

发布于2016年01月30日 | 暂无评论 | 1,661阅读 | CDQ分治

题目描述

有n朵花，每朵花有三个属性：花形(s)、颜色(c)、气味(m)，又三个整数表示。现要对每朵花评级，一朵花的级别是它拥有的美丽能超过的花的数量。定义一朵花A比另一朵花B要美丽，当且仅当Sa>=Sb,Ca>=Cb,Ma>=Mb。显然，两朵花可能有同样的属性。需要统计出评出每个等级的花的数量。

输入格式

第一行为N,K (1 <= N <= 100,000, 1 <= K <= 200,000 ), 分别表示花的数量和最大属性值。

以下N行，每行三个整数si, ci, mi (1 <= si, ci, mi <= K)，表示第i朵花的属性。

输出格式

包含N行，分别表示评级为0...N-1的每级花的数量。

题目解析

伟大的CDQ，您真是我们的红太阳！

再一次被CDQ分治的力量所折服。本题是裸的三维数点问题，类比于二维数点，我们用降维的思想来做。先去重，第一维直接排序，后两维套用CDQ分治，用树状数组维护即可。

/**************************************************************
    Problem: 3262
    User: frank_c1
    Language: C++
    Result: Accepted
    Time:3184 ms
    Memory:5964 kb
****************************************************************/
 
#include <set>
#include <map>
#include <queue>
#include <ctime>
#include <cmath>
#include <cstdio>
#include <vector>
#include <string>
#include <cctype>
#include <bitset>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <iostream>
#include <algorithm>
#define REP(i,a,b) for(int i=(a);i<=(b);i++)
#define PER(i,a,b) for(int i=(a);i>=(b);i--)
#define RVC(i,S) for(int i=0;i<(S).size();i++)
#define RAL(i,u) for(int i=fr[u];i!=-1;i=e[i].next)
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
   
template<class T> inline
void read(T& num) {
    bool start=false,neg=false;
    char c;
    num=0;
    while((c=getchar())!=EOF) {
        if(c=='-') start=neg=true;
        else if(c>='0' && c<='9') {
            start=true;
            num=num*10+c-'0';
        } else if(start) break;
    }
    if(neg) num=-num;
}
/*============ Header Template ============*/
 
#define lowbit(x) (x)&(-x)
 
struct node {
    int a,b,c,siz,ans;
    bool operator == (const node& t) const {
        if(a==t.a && b==t.b && c==t.c) return true;
        else return false;
    }
    bool operator != (const node& t) const {return !(*this==t);}
};
 
bool cmpa(node s,node t) {
    if(s.a!=t.a) return s.a<t.a;
    if(s.b!=t.b) return s.b<t.b;
    return s.c<t.c;
}
 
bool cmpb(node s,node t) {
    if(s.b!=t.b) return s.b<t.b;
    return s.c<t.c;
}
 
const int maxn=(int)(1e5)+5;
const int maxk=(int)(2e5)+5;
node A[maxn],T[maxn];
int C[maxn],res[maxn];
int n,mx,tot=0;
 
inline void add(int x,int d) {
    while(x<=mx) {
        C[x]+=d;
        x+=lowbit(x);
    }
}
 
inline int sum(int x) {
    int ret=0;
    while(x>0) {
        ret+=C[x];
        x-=lowbit(x);
    }
    return ret;
}
 
void solve(int l,int r) {
    if(l==r) return;
    int mid=(l+r)>>1;
    solve(l,mid);solve(mid+1,r);
    sort(T+l,T+mid+1,cmpb);
    sort(T+mid+1,T+r+1,cmpb);
    int i=l;
    for(int j=mid+1;j<=r;j++) {
        while(i<=mid && T[i].b<=T[j].b)
            add(T[i].c,T[i].siz),++i;
        T[j].ans+=sum(T[j].c);
    }
    for(int j=l;j<i;j++) add(T[j].c,-T[j].siz);
}
 
int main() {
    read(n);read(mx);
    REP(i,1,n) {
        read(A[i].a);
        read(A[i].b);
        read(A[i].c);
    }
    sort(A+1,A+n+1,cmpa);
    int cnt=0;
    REP(i,1,n) {
        cnt++;
        if(A[i]!=A[i+1]) {
            T[++tot]=A[i];
            T[tot].siz=cnt;
            cnt=0;
        }
    }
    solve(1,tot);
    REP(i,1,tot) 
        res[T[i].ans+T[i].siz-1]+=T[i].siz;
    REP(i,0,n-1) printf("%d\n",res[i]);
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

/**************************************************************

Problem: 3262

User: frank_c1

Language: C++

Result: Accepted

Time:3184 ms

Memory:5964 kb

****************************************************************/

#include <set>

#include <map>

#include <queue>

#include <ctime>

#include <cmath>

#include <cstdio>

#include <vector>

#include <string>

#include <cctype>

#include <bitset>

#include <cstring>

#include <cstdlib>

#include <utility>

#include <iostream>

#include <algorithm>

#define REP(i,a,b) for(int i=(a);i<=(b);i++)

#define PER(i,a,b) for(int i=(a);i>=(b);i--)

#define RVC(i,S) for(int i=0;i<(S).size();i++)

#define RAL(i,u) for(int i=fr[u];i!=-1;i=e[i].next)

using namespace std;

typedef long long LL;

typedef pair<int,int> pii;

template<class T> inline

void read(T& num) {

bool start=false,neg=false;

char c;

num=0;

while((c=getchar())!=EOF) {

if(c=='-') start=neg=true;

else if(c>='0' && c<='9') {

start=true;

num=num*10+c-'0';

} else if(start) break;

}

if(neg) num=-num;

}

/*============ Header Template ============*/

#define lowbit(x) (x)&(-x)

struct node {

int a,b,c,siz,ans;

bool operator == (const node& t) const {

if(a==t.a && b==t.b && c==t.c) return true;

else return false;

}

bool operator != (const node& t) const {return !(*this==t);}

};

bool cmpa(node s,node t) {

if(s.a!=t.a) return s.a<t.a;

if(s.b!=t.b) return s.b<t.b;

return s.c<t.c;

}

bool cmpb(node s,node t) {

if(s.b!=t.b) return s.b<t.b;

return s.c<t.c;

}

const int maxn=(int)(1e5)+5;

const int maxk=(int)(2e5)+5;

node A[maxn],T[maxn];

int C[maxn],res[maxn];

int n,mx,tot=0;

inline void add(int x,int d) {

while(x<=mx) {

C[x]+=d;

x+=lowbit(x);

}

inline int sum(int x) {

int ret=0;

while(x>0) {

ret+=C[x];

x-=lowbit(x);

}

return ret;

}

void solve(int l,int r) {

if(l==r) return;

int mid=(l+r)>>1;

solve(l,mid);solve(mid+1,r);

sort(T+l,T+mid+1,cmpb);

sort(T+mid+1,T+r+1,cmpb);

int i=l;

for(int j=mid+1;j<=r;j++) {

while(i<=mid && T[i].b<=T[j].b)

add(T[i].c,T[i].siz),++i;

T[j].ans+=sum(T[j].c);

}

for(int j=l;j<i;j++) add(T[j].c,-T[j].siz);

}

int main() {

read(n);read(mx);

REP(i,1,n) {

read(A[i].a);

read(A[i].b);

read(A[i].c);

}

sort(A+1,A+n+1,cmpa);

int cnt=0;

REP(i,1,n) {

cnt++;

if(A[i]!=A[i+1]) {

T[++tot]=A[i];

T[tot].siz=cnt;

cnt=0;

}

solve(1,tot);

REP(i,1,tot)

res[T[i].ans+T[i].siz-1]+=T[i].siz;

REP(i,0,n-1) printf("%d\n",res[i]);

return 0;

}

AC. 梦想

[BZOJ 3262] 陌上花开

题目描述

输入格式

输出格式

题目解析

快速访问

随便看看

友情链接

标签