BZOJ3262:陌上花开 & 洛谷3810:三维偏序——题解

http://www.lydsy.com/JudgeOnline/problem.php?id=3262

https://www.luogu.org/problemnew/show/3810

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

——————————————————————————

CDQ分治不那么裸的题吧……?可能我菜。

(事实证明三维偏序是CDQ最常见的表现形式……我是真的菜)

首先如果我们做过POJ2532的话, 那这题的思路就不难想:我们对一个维度进行排序,对于另一个维度树状数组统计比它晓得个数有几个,那我们就能够确定它的等级。

不幸的是,这题有三个维度,排掉一个还剩两个,总不能树状数组套树状数组吧(我也不会写啊……)

这时候我们就想到了神奇的CDQ分治(点击此处获得原理),但是这并没有查询和修改操作啊……

好的我们开始对题目重新理解一下!

首先定义我们的修改操作就是往树状数组里添加/删除节点,我们的查询操作就是查询该点的等级。

那么对于一维肯定是要排序的,在那之后我们把根据一维排好的序当做查询/修改的时间,于是我们就神奇的变成了:先询问(该点等级),再修改(将节点插入)的在线问题。

那么CDQ就可以上了!我们对每个区间的节点的二维排序之后套树状数组查三维即可。

PS1:CDQ具体做法:我们每次添加区间前一半的点,后一半进行查询(原因不好用语言表达,大致意思为一个点到区间前端的这段区间可以由若干个CDQ区间的整个前半组成)

PS2:本题还有一个坑点,即相同的点也算是比自己丑(……),而树状数组对于一串相同的点的查询,只有最后一个点的答案正确,其他的点的答案分别为:倒数第二与ans差1,倒数第三与ans差2……所以我们预处理一下即可。

#include<cmath>
#include<cstdio>
#include<queue>
#include<cctype>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=;
inline int read(){
int X=,w=; char ch=;
while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
while(isdigit(ch)) X=(X<<)+(X<<)+(ch^),ch=getchar();
return w?-X:X;
}
struct flower{
int x;
int y;
int z;
int num;
int ans;
}a[N],b[N];
int ans[N],tree[*N],n,k;
bool cmp(flower a,flower b){
return (a.x<b.x)||(a.x==b.x&&(a.y<b.y||(a.y==b.y&&a.z<b.z)));
}
bool same(flower a,flower b){
return (a.x==b.x&&a.y==b.y&&a.z==b.z);
}
inline int lowbit(int t){return t&(-t);}
void add(int x,int y){//将a[x]+y
for(int i=x;i<=k;i+=lowbit(i))tree[i]+=y;
return;
}
int query(int x){//1-x区间和
int res=;
for(int i=x;i>;i-=lowbit(i))res+=tree[i];
return res;
}
void cdq(int l,int r){
if(l>=r)return;
int mid=(l+r)>>;
cdq(l,mid);cdq(mid+,r);
for(int i=l,j=l,p=mid+;i<=r;i++){
if(j<=mid&&(p>r||a[j].y<=a[p].y))b[i]=a[j++];
else b[i]=a[p++];
}
for(int i=l;i<=r;i++){
a[i]=b[i];
if(a[i].num<=mid)add(a[i].z,);
else a[i].ans+=query(a[i].z);
}
for(int i=l;i<=r;i++)if(a[i].num<=mid)add(a[i].z,-);
return;
}
int main(){
n=read();
k=read();
for(int i=;i<=n;i++){
a[i].x=read();
a[i].y=read();
a[i].z=read();
}
sort(a+,a+n+,cmp);
flower t;int cnt=;
for(int i=n;i>=;i--){
if(same(t,a[i])){
a[i].ans+=cnt;
cnt++;
}
else{
t=a[i];
cnt=;
}
}
for(int i=;i<=n;i++)a[i].num=i;
cdq(,n);
for(int i=;i<=n;i++)ans[a[i].ans]++;
for(int i=;i<n;i++)printf("%d\n",ans[i]);
return ;
}
上一篇:FLASH AS 不显示中文


下一篇:javascript – Selection.addRange()已弃用,将从Chrome中删除