正文 

当前位置： 首页 > java > java教程

bzoj3262：陌上花开&洛谷3810：三维偏序——题解

LuYouQi233 LuYouQi233     2022-10-05     185

关键词：

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=100001;
inline int read(){
    int X=0,w=0; char ch=0;
    while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
    while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),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[2*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=0;
    for(int i=x;i>0;i-=lowbit(i))res+=tree[i];
    return res;
}
void cdq(int l,int r){
    if(l>=r)return;
    int mid=(l+r)>>1;
    cdq(l,mid);cdq(mid+1,r);
    for(int i=l,j=l,p=mid+1;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,1);
    else a[i].ans+=query(a[i].z);
    }
    for(int i=l;i<=r;i++)if(a[i].num<=mid)add(a[i].z,-1);
    return;
}
int main(){
    n=read();
    k=read();
    for(int i=1;i<=n;i++){
    a[i].x=read();
    a[i].y=read();
    a[i].z=read();
    }
    sort(a+1,a+n+1,cmp);
    flower t;int cnt=1;
    for(int i=n;i>=1;i--){
    if(same(t,a[i])){
        a[i].ans+=cnt;
        cnt++;
    }
    else{
        t=a[i];
        cnt=1;
    }
    }
    for(int i=1;i<=n;i++)a[i].num=i;
    cdq(1,n);
    for(int i=1;i<=n;i++)ans[a[i].ans]++;
    for(int i=0;i<n;i++)printf("%d\n",ans[i]);
    return 0;
}

[luogu3810][bzoj3262][陌上花开](代码片段)

题目链接思路听说可以CDQ分治，然后我不会，所以我写树套树首先肯定先按照a拍个序。然后就成了在b，c这两个数组中查询了。用一个树状数组套treap来维护。当插入一个数的时候，就在树状数组的b这个位置的treap里加入一个c。... 查看详情

[bzoj]3263陌上花开洛谷p3810三维偏序||cdq分治&&cdq分治讲解

原题定义一个点比另一个点大为当且仅当这个点的三个值分别大于等于另一个点的三个值。每比一个点大就为加一等级，求每个等级的点的数量。显然的三维偏序问题，CDQ的板子题。CDQ分治：CDQ分治是一种特殊的分治方法，在OI... 查看详情

洛谷p3810模板三维偏序（陌上花开）(cdq分治模板)(代码片段)

在solve(L,R)中，需要先分治solve两个子区间，再计算左边区间修改对右边区间询问的贡献。注意，计算额外的贡献时，两子区间各自内部的顺序变得不再重要（不管怎么样左边区间的都发生在右边之前），于是就少了一维https://www.... 查看详情

bzoj3262陌上花开cdq分治

#include<iostream>#include<cstdio>#include<algorithm>usingnamespacestd;constintN=100005,K=200005;intn,k,tot,t[K],ans[N];structqwe{intx,y,z,con,ans;}a[N];boolcmp1(constqwe&a,const 查看详情

bzoj3262:陌上花开

3262:陌上花开TimeLimit: 20Sec  MemoryLimit: 256MBSubmit: 2761  Solved: 1231[Submit][Status][Discuss]Description有n朵花，每朵花有三个属性：花形(s)、颜色(c)、气味(m)，又三个整数表示。现要对每朵花评级，一朵花的 查看详情

bzoj3262陌上花开

3262:陌上花开TimeLimit: 20Sec  MemoryLimit: 256MBSubmit: 2010  Solved: 898[Submit][Status][Discuss]Description有n朵花，每朵花有三个属性：花形(s)、颜色(c)、气味(m)，又三个整数表示。现要对每朵花评级，一朵花的级 查看详情

[bzoj3262]陌上花开

3262:陌上花开TimeLimit:20Sec  MemoryLimit:256MBSubmit:2497  Solved:1115[Submit][Status][Discuss]Description有n朵花，每朵花有三个属性：花形(s)、颜色(c)、气味(m)，又三个整数表示。现要对每朵花评级，一朵花的级别是它拥有的美丽能... 查看详情

bzoj3262陌上花开cdq分治

3262:陌上花开TimeLimit: 20Sec  MemoryLimit: 256MBSubmit: 2794  Solved: 1250[Submit][Status][Discuss]Description有n朵花，每朵花有三个属性：花形(s)、颜色(c)、气味(m)，又三个整数表示。现要对每朵花评级，一朵花的 查看详情

bzoj3262:陌上花开

//Twenty#include<cstdio>#include<cstdlib>#include<iostream>#include<algorithm>#include<cmath>#include<cstring>#include<queue>#include<vector>#definemid( 查看详情

bzoj3262陌上花开

题解：裸cdq分治一开始处理相同花的时候搞错了，WA了几发#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>usingnamespacestd;constintmaxn=200009;intn,m;intb[maxn],nn;intfsiz;intans[max 查看详情

bzoj3262:陌上花开--cdq分治

3262:陌上花开TimeLimit: 20Sec  MemoryLimit: 256MBDescription有n朵花，每朵花有三个属性：花形(s)、颜色(c)、气味(m)，又三个整数表示。现要对每朵花评级，一朵花的级别是它拥有的美丽能超过的花的数量。定义一朵花A比另... 查看详情

bzoj3262陌上花开（cdq分治）

【BZOJ3262】陌上花开（CDQ分治）题解原来放过这道题目，题面在这里树套树的做法也请点上面这回用CDQ分治做的其实也很简单，对于第一维排序之后显然只有前面的对后面的才会产生贡献那么，使用CDQ分治先分，每次递归子问题... 查看详情

bzoj3262陌上花开

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3262【题解】cdq分治。这题是三维偏序问题。我们先对整体排序，合并相同的，记原来的n为N，剩下的个数为n。然后对于b排序，把a重新编号为1...ncdq分治的时候呢，我们定义过程solve(l... 查看详情

bzoj3262陌上花开

好文艺的题目。自己犯的**错误不想再提了，特别注意这题要求三个都相等时也计入统计，所以就特别处理一下。裸的三位偏序，CDQ+树状数组By：大奕哥1#include<bits/stdc++.h>2usingnamespacestd;3constintN=200005;4constintM=400005;5intn,k,tim,ans... 查看详情

「bzoj」「3262」陌上花开

CDQ分治　　WA：在solve时，对y、z排序以后，没有处理「y、z相同」的情况，也就是说可能（1，2，3）这个点被放到了（2，2，3）的后面，也就是统计答案在前，插入该点在后……也就没有统计到！　　sad1#include<cstdio>2... 查看详情

[bzoj3262]陌上花开分治

题意　　给定三个序列$S=left{s_1,s_2,...,s_n ight}$,$C=left{c_1,c_2,...,c_n ight}$,$M=left{m_1,m_2,...,m_n ight}$.　　对任意$i$,求$level_i=sum_{j ei,1lejlen}[s_iges_j][c_igec_j][m_igem_j]$. 分析　 查看详情

bzoj3262陌上花开cdq+树状数组

【bzoj3262】陌上花开Description有n朵花，每朵花有三个属性：花形(s)、颜色(c)、气味(m)，又三个整数表示。现要对每朵花评级，一朵花的级别是它拥有的美丽能超过的花的数量。定义一朵花A比另一朵花B要美丽，当且仅当Sa>=Sb,Ca&g... 查看详情

陌上花开（bzoj3262）

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