BZOJ.3262.陌上花开([模板]CDQ分治 三维偏序)

题目链接 BZOJ3262
洛谷P3810

/*
5904kb  872ms
对于相邻x,y,z相同的元素要进行去重，并记录次数算入贡献(它们之间产生的答案是一样的，但不去重会。。) 
*/
#include <cstdio>
#include <cctype>
#include <algorithm>
#define gc() getchar()
#define lb(x) (x)&-(x)
const int N=1e5+5;

int n,Ans[N];
int read();
struct Operation
{
    int x,y,z,cnt,res;
    inline void Init(){
        x=read(),y=read(),z=read(),cnt=1;
    }
    bool operator <(const Operation &a)const{
        return x==a.x?(y==a.y?z<a.z:y<a.y):x<a.x;
    }
}q[N],tmp[N];

namespace BIT
{//三维:树状数组 
    int Max,t[N<<1];
    void Add(int p,int v){
        while(p<=Max) t[p]+=v,p+=lb(p);
    }
    int Query(int p){
        int res=0;
        while(p) res+=t[p],p-=lb(p);
        return res;
    }
}
inline int read()
{
    int now=0,f=1;register char c=gc();
    for(;!isdigit(c);c=gc()) if(c=='-') f=-1;
    for(;isdigit(c);now=now*10+c-'0',c=gc());
    return now*f;
}
void CDQ(int l,int r)
{//处理第二维 
    if(l<r)
    {
        int m=l+r>>1; CDQ(l,m), CDQ(m+1,r);
        int p1=l,p2=m+1,cnt=0;
        while(p1<=m&&p2<=r)
        {
            if(q[p1].y<=q[p2].y)//这里的条件要是<= 
                BIT::Add(q[p1].z,q[p1].cnt), tmp[cnt++]=q[p1++];
            else 
                q[p2].res+=BIT::Query(q[p2].z), tmp[cnt++]=q[p2++];
        }
        while(p1<=m) BIT::Add(q[p1].z,q[p1].cnt), tmp[cnt++]=q[p1++];//先加上 方便再减去 
        while(p2<=r) q[p2].res+=BIT::Query(q[p2].z), tmp[cnt++]=q[p2++];
        for(int i=l; i<=m; ++i) BIT::Add(q[i].z,-q[i].cnt);
        for(int i=0; i<cnt; ++i) q[l+i]=tmp[i];
    }
}

int main()
{
    n=read(),BIT::Max=read();
    for(int i=1; i<=n; ++i) q[i].Init();
    std::sort(q+1,q+1+n);
    int cnt=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) ++q[cnt].cnt;
        else q[++cnt]=q[i];
    CDQ(1,cnt);
    for(int i=1; i<=cnt; ++i) Ans[q[i].res+q[i].cnt-1]+=q[i].cnt;//f[i]为res[i]+cnt[i]-1, 贡献为cnt[i] 
    for(int i=0; i<n; ++i) printf("%d\n",Ans[i]);

    return 0;
}

3.30：

/*
5904kb  840ms
是对x,y,z都相同的元素去重，不是对z。。sb了。
去重后的贡献是q[p].cnt!
*/
#include <cstdio>
#include <cctype>
#include <algorithm>
#define gc() getchar()
#define lb(x) (x)&-(x)
const int N=1e5+5,MAXN=2e5+5;

int n,Ans[N];
int read();
struct Node
{
    int x,y,z,cnt,ans;
    void Init(){
        x=read(),y=read(),z=read(),cnt=1;
    }
    bool operator <(const Node &a)const{
        return x==a.x?(y==a.y?z<a.z:y<a.y):x<a.x;
    }
}q[N],tmp[N];

inline int read()
{
    int now=0;register char c=gc();
    for(;!isdigit(c);c=gc());
    for(;isdigit(c);now=now*10+c-'0',c=gc());
    return now;
}
namespace BIT
{
    int n,val[MAXN];
    inline void Add(int p,int v){
        while(p<=n) val[p]+=v,p+=lb(p);
    }
    inline int Query(int p){
        int res=0;
        while(p) res+=val[p],p-=lb(p);
        return res;
    }
    inline void Clear(int p){
        while(p<=n)
            if(val[p]) val[p]=0,p+=lb(p);
            else break;
    }
}
void CDQ(int l,int r)
{
    if(l<r){
        int m=l+r>>1; CDQ(l,m), CDQ(m+1,r);
        int p1=l,p2=m+1,t=0;
        while(p1<=m&&p2<=r)
        {
            if(q[p1].y<=q[p2].y) BIT::Add(q[p1].z,q[p1].cnt), tmp[t++]=q[p1++];//只是排y，别去管什么z。。
            else q[p2].ans+=BIT::Query(q[p2].z), tmp[t++]=q[p2++];
        }
        if(p1<=m){
            for(int i=l; i<p1; ++i) BIT::Clear(q[i].z);
            while(p1<=m) tmp[t++]=q[p1++];
        }
        else if(p2<=r){
            while(p2<=r) q[p2].ans+=BIT::Query(q[p2].z), tmp[t++]=q[p2++];
            for(int i=l; i<=m; ++i) BIT::Clear(q[i].z);
        }
        for(int i=0; i<t; ++i) q[l+i]=tmp[i];
    }
}

int main()
{
    n=read(),BIT::n=read();
    for(int i=1; i<=n; ++i) q[i].Init();
    std::sort(q+1,q+1+n);
    int cnt=1;
    for(int i=2; i<=n; ++i)
        if(q[i].z!=q[i-1].z||q[i].y!=q[i-1].y||q[i].x!=q[i-1].x) q[++cnt]=q[i];
        else ++q[cnt].cnt;
    CDQ(1,cnt);
    for(int i=1; i<=cnt; ++i) Ans[q[i].ans+q[i].cnt-1]+=q[i].cnt;
    for(int i=0; i<n; ++i) printf("%d\n",Ans[i]);

    return 0;
}

19.4.5
上BZOJ前三啦。

//6196KB    688MS
#include <cstdio>
#include <cctype>
#include <algorithm>
#define gc() getchar()
#define MAXIN 300000
//#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
typedef long long LL;
const int N=1e5+5,M=2e5+5;

int Ans[N];
char IN[MAXIN],*SS=IN,*TT=IN;
struct Node
{
    int x,y,z,cnt,ans;
    bool operator <(const Node &a)const
    {
        return x==a.x?(y==a.y?z<a.z:y<a.y):x<a.x;
    }
    bool operator !=(const Node &a)const
    {
        return x!=a.x||y!=a.y||z!=a.z;
    }
}q[N],tmp[N];
struct BIT
{
    int n,t[M];//M!
    #define lb(x) (x&-x)
    inline void Add(int p,int v)
    {
        for(; p<=n; p+=lb(p)) t[p]+=v;
    }
    inline int Query(int p)
    {
        int res=0;
        for(; p; p^=lb(p)) res+=t[p];
        return res;
    }
    inline void Clear(int p)
    {
        for(; p<=n&&t[p]; p+=lb(p)) t[p]=0;
    }
}T;

inline int read()
{
    int now=0;register char c=gc();
    for(;!isdigit(c);c=gc());
    for(;isdigit(c);now=now*10+c-48,c=gc());
    return now;
}
void CDQ(int l,int r)
{
    if(l<r)
    {
        int m=l+r>>1; CDQ(l,m), CDQ(m+1,r);
        int p1=l,p2=m+1,p=l;
        while(p1<=m&&p2<=r)
        {
            if(q[p1].y<=q[p2].y) T.Add(q[p1].z,q[p1].cnt), tmp[p++]=q[p1++];//q[p1].cnt!
            else q[p2].ans+=T.Query(q[p2].z), tmp[p++]=q[p2++];
        }
        while(p2<=r) q[p2].ans+=T.Query(q[p2].z), tmp[p++]=q[p2++];
        for(int i=l; i<p1; ++i) T.Clear(q[i].z);//<p1
        while(p1<=m) tmp[p++]=q[p1++];
        for(int i=l; i<=r; ++i) q[i]=tmp[i];
    }
}

int main()
{
    int n=read(); T.n=read();
    for(int i=1; i<=n; ++i) q[i]=(Node){read(),read(),read(),1,0};//cnt不能是0啊= = 
    std::sort(q+1,q+1+n); int cnt=1;
    for(int i=2; i<=n; ++i)
        if(q[i]!=q[i-1]) q[++cnt]=q[i];
        else ++q[cnt].cnt;
    CDQ(1,cnt);
    for(int i=1; i<=cnt; ++i) Ans[q[i].ans+q[i].cnt-1]+=q[i].cnt;
    for(int i=0; i<n; ++i) printf("%d\n",Ans[i]);

    return 0;
}