题目链接
思路
听说可以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; }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/605967.html