zcmimi's blog
avatar
zc
2020-03-20 21:22:00
  • 本文总阅读量
查看原题

点击跳转

#include<bits/stdc++.h>
typedef long long ll;typedef double db;typedef unsigned long long ull;
template <class T>inline T min(T x,T y){return x<y?x:y;}
template <class T>inline T max(T x,T y){return x>y?x:y;}
namespace IN{const int str=1<<20;static char in_buf[str],*in_s,*in_t;bool __=0;inline char gc(){return (in_s==in_t)&&(in_t=(in_s=in_buf)+fread(in_buf,1,str,stdin)),in_s==in_t?EOF:*in_s++;}template<typename T>inline void in(T &x){if(__)return;char c=gc();bool f=0;while(c!=EOF&&(c<'0'||c>'9'))f^=(c=='-'),c=gc();if(c==EOF){__=1;return;}x=0;while(c!=EOF&&'0'<=c&&c<='9')x=x*10+c-48,c=gc();if(c==EOF)__=1;if(f)x=-x;}template<typename T,typename ... arr>inline void in(T &x,arr & ... y){in(x),in(y...);}}using namespace IN;
namespace OUT{const char ln='\n';const int str=1<<20;static char out_buf[str],*out_s=out_buf,*out_t=out_buf+str;inline void flush(){fwrite(out_buf,1,out_s-out_buf,stdout);out_s=out_buf;}inline void pt(char c){(out_s==out_t)?(fwrite(out_s=out_buf,1,str,stdout),*out_s++=c):(*out_s++=c);}template<typename T>inline void out(T x){if(!x){pt('0');return;}if(x<0)pt('-'),x=-x;char a[50],t=0;while(x)a[t++]=x%10,x/= 10;while(t--)pt(a[t]+'0');}template<typename T,typename ... arr>inline void out(T x,arr & ... y){out(x),out(y...);}}using namespace OUT;
const int N=100011,inf=2122219134;
using std::sort;
int d,n,k,s[N<<1],ans[N];
struct node{int x,y,z,ans,w;}b[N],a[N];
bool cmpx(node x,node y){
    if(x.x!=y.x)return x.x<y.x;
    if(x.y!=y.y)return x.y<y.y;
    return x.z<y.z;
}
bool cmpy(node x,node y){
    if(x.y!=y.y)return x.y<y.y;
    return x.z<y.z;
}
inline void add(int x,int v){for(int i=x;i<=k;i+=i&-i)s[i]+=v;}
inline int ask(int x){
    int res=0;
    for(int i=x;i;i-=i&-i)res+=s[i];
    return res;
}
inline void cdq(int l,int r){
    if(l>=r)return;
    int m=(l+r)>>1,j=l;
    cdq(l,m);cdq(m+1,r);
    sort(a+l,a+m+1,cmpy);
    sort(a+m+1,a+r+1,cmpy);
    for(int i=m+1;i<=r;++i){
        for(;j<=m&&a[j].y<=a[i].y;++j)
            add(a[j].z,a[j].w);
        a[i].ans+=ask(a[i].z);
    }
    for(int i=l;i<=j-1;++i)add(a[i].z,-a[i].w);
}
int main(){
    in(d,k);
    for(int i=1;i<=d;++i)in(b[i].x,b[i].y,b[i].z);
    sort(b+1,b+d+1,cmpx);
    for(int i=1,c=1;i<=d;++i,++c)
    if(b[i].x!=b[i+1].x||b[i].y!=b[i+1].y||b[i].z!=b[i+1].z)
        a[++n]=b[i],a[n].w=c,c=0;
    cdq(1,n);
    for(int i=1;i<=n;++i)ans[a[i].ans+a[i].w]+=a[i].w;
    for(int i=1;i<=d;++i)out(ans[i]),pt('\n');
    flush();
}
LG 3810 【模板】三维偏序(陌上花开)
comment评论
Search
search