题解:cdq分治的模板题 .....没考虑到重复的情况 加上 好困啊....一直写挂 思路还是很清晰 难受TAT
#include <bits/stdc++.h>
const int MAXN=1e5+10;
using namespace std;
struct FastIO
{
static const int S=200;
int wpos;
char wbuf[S];
FastIO():wpos(0){}
inline int xchar()
{
static char buf[S];
static int len=0,pos=0;
if(pos==len) pos=0,len=fread(buf,1,S,stdin);
if(pos==len) exit(0);
return buf[pos++];
}
inline int read()
{
int s=1,c=xchar(),x=0;
while(c<=32) c=xchar();
if(c=='-') s=-1,c=xchar();
for(;'0'<=c&&c<='9';c=xchar()) x=x*10+c-'0';
return x*s;
}
~FastIO()
{
if(wpos) fwrite(wbuf,1,wpos,stdout),wpos=0;
}
}io;
typedef struct node{
int x,y,z,ans,cnt,id;
}node;
node que[MAXN],q[MAXN],ed[MAXN];
int ans1[MAXN],ans2[MAXN];
bool cmp(node x,node y){
if(x.x==y.x&&x.y==y.y)return x.z<y.z;
else if(x.x==y.x)return x.y<y.y;
return x.x<y.x;
}
int n,k,sum[MAXN<<1];
int get_id(int x){return x&(-x);}
void add(int x,int vul){for(;x<=k;x+=get_id(x))sum[x]+=vul;}
int Sum(int x){
int ans=0;
for(;x>0;x-=get_id(x))ans+=sum[x];
return ans;
}
void clear(int x){for(;x<=k;x+=get_id(x))sum[x]=0;}
void merge(int l,int mid,int r){
int i=l;int j=mid+1;int cnt=0;
while(i<=mid&&j<=r){
while(i<=mid&&que[i].y<=que[j].y){add(que[i].z,ans2[que[i].id]);ed[++cnt]=que[i];i++;}
ans1[que[j].id]+=Sum(que[j].z);ed[++cnt]=que[j];
j++;
}
for(;j<=r;j++)ans1[que[j].id]+=Sum(que[j].z),ed[++cnt]=que[j];
for(;i<=mid;i++)ed[++cnt]=que[i];
for(int i=1;i<=cnt;i++)que[l+i-1]=ed[i],clear(ed[i].z);
}
void cdq(int l,int r){
if(l>=r)return ;
int mid=(l+r)>>1;
cdq(l,mid);cdq(mid+1,r);
merge(l,mid,r);
}
int ans[MAXN];
int main(){
n=io.read();k=io.read();
for(int i=1;i<=n;i++)q[i].x=io.read(),q[i].y=io.read(),q[i].z=io.read(),q[i].ans=0;
sort(q+1,q+n+1,cmp);
int cnt=0;que[++cnt]=q[1];int last=1;que[cnt].id=1;
for(int i=2;i<=n;i++){
if(q[i].x!=q[i-1].x||q[i].y!=q[i-1].y||q[i].z!=q[i-1].z){
que[++cnt]=q[i];que[cnt].id=cnt;ans2[cnt-1]=i-last;last=i;
}
}
ans2[cnt]=n+1-last;
cdq(1,cnt);
for(int i=1;i<=cnt;i++)ans[ans1[i]+ans2[i]-1]+=ans2[i];
for(int i=0;i<n;i++)printf("%d
",ans[i]);
}
3262: 陌上花开
Time Limit: 20 Sec Memory Limit: 256 MBSubmit: 4024 Solved: 1899
[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
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
1
3
0
1
0
1
0
0
1