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

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

阅读量：4318 次

发布时间：2019-06-06

本文共 2344 字，大约阅读时间需要 7 分钟。

/*5904kb  872ms对于相邻x,y,z相同的元素要进行去重，并记录次数算入贡献(它们之间产生的答案是一样的，但不去重会。。) */#include 
    
     #include 
     
      #include 
      
       #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
       
        
         
          >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

3.30：

/*5904kb  840ms是对x,y,z都相同的元素去重，不是对z。。sb了。去重后的贡献是q[p].cnt!*/#include 
    
     #include 
     
      #include 
      
       #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
       
        
         
          >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

19.4.5

上BZOJ前三啦。

//6196KB    688MS#include 
    
     #include 
     
      #include 
      
       #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
       
        
         
          >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