BZOJ 3262: 陌上花开 [CDQ分治 三维偏序]

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的每级花的数量。


$fuck$太坑了!!!!!!!!!

各种修改比较操作各种修改细节最后发现是因为我去重之后把$n$改变了然而人家输出需要原来的$n$!!!!!!!!!!!!!!!!!

裸的三维偏序

$a$排序,$b$ $CDQ$分治,$c$树状数组

注意需要去重

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const int N=2e5+5;
inline int read(){
    char c=getchar();int x=0,f=1;
    while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();}
    while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();}
    return x*f;
}
int n,maxVal;
struct Operation{
    int a,b,c,w;
    int f;
    bool operator <(const Operation &r)const{
        //return a<r.a || (a==r.a&&b<r.b) || (a==r.a&&b==r.b&&c<r.c);
        return (a==r.a&&b==r.b) ? c<r.c : (a==r.a?b<r.b:a<r.a);
    }
}a[N],t[N];
int c[N];
inline int lowbit(int x){return x&-x;}
inline void add(int p,int v){for(;p<=maxVal;p+=lowbit(p)) c[p]+=v;}
inline int sum(int p){
    int re=0;
    for(;p;p-=lowbit(p)) re+=c[p];
    return re;
}
int ans[N];
void CDQ(int l,int r){
    if(l==r) return;
    int mid=(l+r)>>1;
    CDQ(l,mid);CDQ(mid+1,r);
    int i=l,j=mid+1,p=l;
    while(i<=mid||j<=r){
        if(j>r||(i<=mid&&a[i].b<=a[j].b)) add(a[i].c,a[i].w),t[p++]=a[i++];
        else a[j].f+=sum(a[j].c),t[p++]=a[j++];
    }
    for(int i=l;i<=mid;i++) add(a[i].c,-a[i].w);
    for(int i=l;i<=r;i++) a[i]=t[i];
}
int main(){
    freopen("in","r",stdin);
    n=read();maxVal=read();
    for(int i=1;i<=n;i++)
        a[i].a=read(),a[i].b=read(),a[i].c=read(),a[i].w=1;
    sort(a+1,a+1+n);

    int p=1;
    for(int i=2;i<=n;i++){
        if(a[i].a==a[p].a&&a[i].b==a[p].b&&a[i].c==a[p].c) a[p].w++;
        else a[++p]=a[i];
    }
    int nnnnn=n;
    n=p;

    CDQ(1,n);
    for(int i=1;i<=n;i++) ans[a[i].f+a[i].w-1]+=a[i].w;
    for(int i=0;i<=nnnnn-1;i++) printf("%d\n",ans[i]);
}


时间: 02-23

BZOJ 3262: 陌上花开 [CDQ分治 三维偏序]的相关文章

bzoj 3262: 陌上花开 -- CDQ分治

3262: 陌上花开 Time Limit: 20 Sec  Memory Limit: 256 MB Description 有n朵花,每朵花有三个属性:花形(s).颜色(c).气味(m),又三个整数表示.现要对每朵花评级,一朵花的级别是它拥有的美丽能超过的花的数量.定义一朵花A比另一朵花B要美丽,当且仅当Sa>=Sb,Ca>=Cb,Ma>=Mb.显然,两朵花可能有同样的属性.需要统计出评出每个等级的花的数量. Input 第一行为N,K (1 <= N <= 100,00

COGS 2479. [HZOI 2016]偏序 [CDQ分治套CDQ分治 四维偏序]

传送门 给定一个有n个元素的序列,元素编号为1~n,每个元素有三个属性a,b,c,求序列中满足i<j且ai<aj且bi<bj且ci<cj的数对(i,j)的个数. 对于100%的数据,1<=n<=50000,保证所有的ai.bi.ci分别组成三个1~n的排列. $CDQ$分治套$CDQ$分治也不是很难嘛 对于本题,设四维$a,b,c,d$ $Sort\ at\ a$ $CDQ(l,r)$ $\quad CDQ(l,mid)$ $\quad CDQ(mid+1,r)$ $\

BZOJ3262陌上花开 CDQ分治_BIT+Treap

三个属性, 第一个属性用cdq分治处理, 以第一个属性为关键字从小到大排序, 那么考虑一朵花的等级, 只需考虑排在其前面的花的其他属性(特殊情况是有相同的花,根据题意,对一段相同的花,以排在最后的一朵花的答案为准), 第二三维可以用树状数组加Treap解决, 以每朵花第二属性数值作为位置(因为最大属性k < 2e5, 可以不用离散化, 直接用属性的数值对应树状数组中的下标), 树状数组的每个节点建一颗Treap, 这颗Treap里存的是相应区间里的花的第三个属性, 询问时类似于树状数组求前缀和,

bzoj 3262: 陌上花开

//Twenty #include<cstdio> #include<cstdlib> #include<iostream> #include<algorithm> #include<cmath> #include<cstring> #include<queue> #include<vector> #define mid ((l+r)>>1) const int maxn=200005; using

萌萌哒cdq分治

cdq分治的思想非常简单, 就是每次分别递归处理在左半边区间内和右半边区间内答案的贡献, 然后像归并排序一样把左半边和有半边合起来, 顺带统计一下左半边区间中的修改对右半边区间中的询问做出的贡献. 归并排序求逆序对就是cdq分治最简单的应用了. 容易分析得出应用到cdq分治时需要满足这些条件:每个修改对于每个询问的影响都是独立的: 我们可以快速地统计出来一堆指定修改操作对一个询问总共的贡献. 经典的应用比如说数点问题. bzoj 3262: 陌上花开 是最简单的三维数点, 这时候直接把第一维排一

初学CDQ分治-NEU1702

关于CDQ分治,首先需要明白分治的复杂度. T(n) = 2T(n/2)+O(kn), T(n) = O(knlogn) T(n) = 2T(n/2)+O(knlogn), T(n) = O(knlog^2n) T(n) = 2T(n/2)+O(k), T(n) = O(kn) 那么我们要处理[l, r]内的询问,我们可以分别处理[l, m]和[m+1, r]的询问,然后以较小的复杂度计算出[l, m]对[m+1, r]的贡献. 最简单的cdq就是三维偏序问题. 两点(x1, y1, z1)和(

P2433 - 【BZOJ 3262三维偏序】陌上花开------三维偏序

P2433 - [BZOJ 3262三维偏序]陌上花开 Description 有n朵花,每朵花有三个属性:花形(s).颜色(c).气味(m),又三个整数表示.现要对每朵花评级,一朵花的级别是它拥有的美丽能超过的花的数量. 定义一朵花A比另一朵花B要美丽,当且仅当Sa>=Sb,Ca>=Cb,Ma>=Mb.显然,两朵花可能有同样的属性.需要统计出评出每个等级的花的数量. Input 第一行为N,K (1 <= N <= 100,000, 1 <= K <= 200,

BZOJ 3295:[Cqoi2011]动态逆序对(三维偏序 CDQ分治+树状数组)

http://www.lydsy.com/JudgeOnline/problem.php?id=3295 题意:简单明了. 思路:终于好像有点明白CDQ分治处理三维偏序了.把删除操作看作是插入操作,那么可以按照插入的时间顺序看作是一维x,插入的数在原本序列的下标是一维y,插入的数本身是一维z.那么问题可以转化成每插入一个数(xx,yy,zz),求有多少个数(x,y,z)使得 x < xx,y < yy,z > zz .一开始先对 x 进行排序,然后进行CDQ分治.这样可以干掉一维,保证随

HDU 5618:Jam&#39;s problem again(CDQ分治+树状数组处理三维偏序)

http://acm.hdu.edu.cn/showproblem.php?pid=5618 题意:-- 思路:和NEUOJ那题一样的.重新写了遍理解了一下,算作处理三维偏序的模板了. 1 #include <cstdio> 2 #include <algorithm> 3 #include <iostream> 4 #include <cstring> 5 using namespace std; 6 #define INF 0x3f3f3f3f 7 #d