c/c++语言开发共享[luogu3810][bzoj3262][陌上花开]

题目链接

思路

听说可以cdq分治，然后我不会，所以我写树套树

首先肯定先按照a拍个序。然后就成了在b，c这两个数组中查询了。用一个树状数组套treap来维护。当插入一个数的时候，就在树状数组的b这个位置的treap里加入一个c。然后查询的时候就直接把小于等于c的数的个数进行前缀和就行了。

注意题目里面是小于等于。所以在按照a加入的时候，要把a相同的数一起加进去。

代码

/* * @author: wxyww * @date:   2018-12-11 14:01:32 * @last modified time: 2018-12-11 14:28:01 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cmath> #include<ctime> #include<bitset> #include<map> #include<algorithm> using namespace std; typedef long long ll; const int n = 100000 + 100,m = 200000 + 100; #define ls tr[cur].ch[0] #define rs tr[cur].ch[1] ll read() {     ll x=0,f=1;char c=getchar();     while(c<'0'||c>'9') {         if(c=='-') f=-1;         c=getchar();     }     while(c>='0'&&c<='9') {         x=x*10+c-'0';         c=getchar();     }     return x*f; } struct node {     int a,b,c; }e[n]; bool operator < (const node &x,const node &y) {     return x.a < y.a; } int rt[n]; int tot = 0; namespace treap {     struct node {         int ch[2],id,val,siz,cnt;     }tr[m * 30];     void up(int cur) {         tr[cur].siz = tr[ls].siz + tr[rs].siz + tr[cur].cnt;     }     void rotate(int &cur,int f) {         int son = tr[cur].ch[f];         tr[cur].ch[f] = tr[son].ch[f ^ 1];         tr[son].ch[f ^ 1] = cur;         up(cur);cur = son;up(cur);     }     void insert(int &cur,int val) {         if(!cur) {             cur = ++tot;             tr[cur].val = val;             tr[cur].cnt = tr[cur].siz = 1;             tr[cur].id = rand();             return;         }         tr[cur].siz++;         if(tr[cur].val == val) {tr[cur].cnt++;return;}         int d = val > tr[cur].val;         insert(tr[cur].ch[d],val);         if(tr[tr[cur].ch[d]].id < tr[cur].id) rotate(cur,d);     }     int rank(int cur,int val) {         int ans = 0;         while(cur) {             if(val == tr[cur].val) return ans + tr[ls].siz + tr[cur].cnt;             if(val > tr[cur].val) ans += tr[ls].siz + tr[cur].cnt,cur = rs;             else cur = ls;         }         return ans;     } } using namespace treap; int tree[m],k; void add(int pos,int c) {     while(pos <= k) {         insert(tree[pos],c);         pos += pos & -pos;     } } int query(int pos,int x) {     int ans = 0;     while(pos >= 1) {         ans += rank(tree[pos],x);         pos -= pos & -pos;     }     return ans; } int have_ad[n]; int ans[n]; int main() {      int n = read();k = read();     for(int i = 1;i <= n;++i) e[i].a = read(),e[i].b = read(),e[i].c = read();     sort(e + 1,e + n + 1);          for(int i = 1;i <= n;++i) {         if(!have_ad[i]) add(e[i].b,e[i].c);         int js = 1;         while(e[i + js].a == e[i].a && !have_ad[i]) {             have_ad[i + js] = 1;             add(e[i + js].b,e[i + js].c);             js++;         }         have_ad[i] = 1;         ans[query(e[i].b,e[i].c)]++;     }     for(int i = 1;i <= n;++i) printf("%dn",ans[i]);     return 0; }