bzoj3262: 陌上花开 树套树

链接

https://www.lydsy.com/JudgeOnline/problem.php?id=3262

思路

CDQ版本稍后再说
二维偏序排序用树状数组求就可以
而三维之后就不可以了，但我们可以在BIT上维护一个功能强大的treap
维护多出来的一维c

BIT套treap
a排序
BIT维护b
treap维护c

错误

需要注意的是，重复元素就不能挨个求了，他们的贡献是最后一个的贡献*数量，注意思考

代码

#include <iostream>
#include <algorithm>
#include <ctime>
#include <cstdlib>
#include <cstdio>
using namespace std;
const int N=2e5+7;
int read() {
    int x=0,f=1;char s=getchar();
    for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;
    for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
    return x*f;
}
#define AA first
#define BB second.first
#define CC second.second
pair<int,pair<int,int> > x[N];
int n,m;
namespace treap {
    int ch[N*40][2],val[N*40],pri[N*40],siz[N*40],cnt;
    int make_new(int k) {
        val[++cnt]=k,pri[cnt]=rand(),siz[cnt]=1;
        return cnt;
    }
    void pushup(int rt) {
        siz[rt]=siz[ch[rt][0]]+siz[ch[rt][1]]+1;
    }
    int merge(int x,int y) {
        if(!x||!y) return x+y;
        if(pri[x]<pri[y]) {
            ch[x][1]=merge(ch[x][1],y);
            pushup(x);
            return x;
        } else {
            ch[y][0]=merge(x,ch[y][0]);
            pushup(y);
            return y;
        }
    }
    void split(int now,int &x,int &y,int k) {
        if(!now) x=y=0; 
        else {
            if(val[now]<=k)
                x=now,split(ch[now][1],ch[x][1],y,k);
            else 
                y=now,split(ch[now][0],x,ch[y][0],k);
            pushup(now);
        }
    }
    int k_th(int now,int k) {
        while(233) {
            if(siz[ch[now][0]]+1==k) return now;
            if(siz[ch[now][0]]>=k) now=ch[now][0];
            else k-=siz[ch[now][0]]+1,now=ch[now][1];
        }
    }
    void insert(int &now,int w) {
        int x,y;
        split(now,x,y,w);
        now=merge(merge(x,make_new(w)),y);
    }
    int query(int now,int k) {
        int x,y;
        split(now,x,y,k);
        int ans=siz[x];
        now=merge(x,y);
        return ans;
    }
}
namespace BIT {
    int rt[N];
    void add(int b,int c) {
        for(int i=b;i<=m;i+=(i&-i))
            treap::insert(rt[i],c);
    }
    int query(int b,int c) {
        int ans=0;
        for(int i=b;i>=1;i-=(i&-i))
            ans+=treap::query(rt[i],c);
        return ans;
    }
}
int ans[N];
int main() {
    n=read(),m=read();
    for(int i=1;i<=n;++i) x[i].AA=read(),x[i].BB=read(),x[i].CC=read();
    sort(x+1,x+1+n);
    int js=1;
    for(int i=1;i<=n;++i) {
        if(x[i]==x[i+1]) js++;
        else ans[BIT::query(x[i].BB,x[i].CC)]+=js,js=1;     
        BIT::add(x[i].BB,x[i].CC);  
    }
    for(int i=0;i<n;++i) printf("%d\n",ans[i]);
    return 0;
}