三维偏序模板

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 
 5 ll read(){
 6     ll x=0,f=1;char c=getchar();
 7     while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}
 8     while(c>='0' && c<='9'){x=x*10+c-'0';c=getchar();}
 9     return x*f;
10 }
11 
12 struct Node{
13     int a,b,c;
14     int ans,cnt;
15     bool operator < (const Node &ano) const{
16         if(a!=ano.a) return a<ano.a;
17         else if(b!=ano.b) return b<ano.b;
18         else return c<ano.c;
19     }
20     bool operator <=(const Node &ano) const{
21         if(a<=ano.a && b<=ano.b && c<=ano.c) return 1;
22     }
23     bool operator ==(const Node &ano) const{
24         return a==ano.a && b==ano.b && c==ano.c;
25     }
26 } a[100100],put[100100];
27 int n,k;
28 int ans[100100];
29 
30 #define lowbit(x) (x&-x)
31 struct Bit{
32     int a[200200];
33 
34     void add(int pos,int val){
35         //cout<<"add "<<pos<<' '<<val<<endl;
36         while(pos<=200000){
37             a[pos]+=val;
38             pos+=lowbit(pos);
39         }
40     }
41 
42     int ask(int pos,int ret=0){
43         //cout<<"ask "<<pos<<' ';
44         while(pos){
45             ret+=a[pos];
46             pos-=lowbit(pos);
47         }
48         //cout<<ret<<endl;
49         return ret;
50     }
51 } BIT;
52 
53 void solve(int l,int r){
54     //cout<<l<<' '<<r<<endl;
55     if(l>=r) return;
56     int md=(l+r)>>1;
57     solve(l,md),solve(md+1,r);
58     int pos=l,top=l;
59     for(int i=md+1;i<=r;i++){
60         while(a[i].b>=a[pos].b && pos<=md){BIT.add(a[pos].c,a[pos].cnt);put[top++]=a[pos++];}
61         a[i].ans+=BIT.ask(a[i].c);put[top++]=a[i];
62     }
63     for(int i=l;i<pos;i++)
64         BIT.add(a[i].c,-a[i].cnt);
65     while(pos<=md) put[top++]=a[pos++];
66     for(int i=l;i<=r;i++)
67         a[i]=put[i];
68 }
69 
70 int main(){
71 #ifdef LZT
72     freopen("in","r",stdin);
73 #endif
74     n=read(),k=read();
75     for(int i=1;i<=n;i++)
76         a[i].a=read(),a[i].b=read(),a[i].c=read(),a[i].cnt=1;
77     sort(a+1,a+n+1);
78     int cnt=1;
79     for(int i=2;i<=n;i++){
80         if(a[cnt]==a[i]) a[cnt].cnt++; else a[++cnt]=a[i];
81     }
82     //for(int i=1;i<=cnt;i++)
83     //    cout<<a[i].a<<' '<<a[i].b<<' '<<a[i].c<<' '<<a[i].cnt<<endl;
84     solve(1,cnt);
85     for(int i=1;i<=cnt;i++)
86         ans[a[i].ans+a[i].cnt-1]+=a[i].cnt;
87     for(int i=0;i<n;i++)
88         printf("%d
",ans[i]);
89     return 0;
90 }
三维偏序 模板

三维偏序模板
