BZOJ 3262 陌上花开树套树 (CDQ分治)

2019-11-06 09:12:57

字体：大中小

来源：转载

供稿：网友

题目大意：有n个三元组(a,b,c)。定义一个三元组A大于另一个三元组B当且仅当A的三个元素都不小于B的三个元素.统计出大于(0~n-1)个三元组的数量。

有三个元素，首先用排序把a弄掉，对于(b,c)两个元素可以看做是平面上的点，利用树套树第一维树状数组，第二维Treap可以解决查找平面上在一个点左下方的点的个数。

当然也可以用CDQ分治来解决，要比树套树快很多~~（然而我就是喜欢树套树）~~

#include <cstdio>#include <algorithm>#define N 100005using namespace std;int n,m;struct Flower { int a,b,c; void scan() {scanf("%d%d%d",&a,&b,&c);} bool Operator < (const Flower& rhs) const { if(a!=rhs.a) return a<rhs.a; if(b!=rhs.b) return b<rhs.b; return c<rhs.c; }}a[N];int ans[N],sum[N];struct Node { Node *ch[2]; int s,r,v,cnt; Node(int,int); Node(){} void maintain(){s=ch[0]->s+ch[1]->s+cnt;} int cmp(int x){ if(x==v) return -1; return x<v ? 0 : 1; }}*null,*root[N*2];Node :: Node(int x,int y):r(x),v(y){s=null ? 1 : 0; ch[0]=ch[1]=null; cnt=s;}void Rotate(Node*& o,int d) { Node* k=o->ch[d^1]; o->ch[d^1]=k->ch[d]; k->ch[d]=o; o->maintain(); k->maintain(); o=k; return ;}void Insert(Node*& o,int x) { int d=o->cmp(x); if(o==null) o=new Node(rand(),x); else if(d==-1) o->cnt++ , o->s++; else { Insert(o->ch[d],x); o->maintain(); if(o->ch[d]->r > o->r) Rotate(o,d^1); } return ;}int Rank(Node* o,int x) { if(o==null) return 0; int d=o->cmp(x); if(d==-1) return o->ch[0]->s+o->cnt; return Rank(o->ch[d],x)+ (d==1 ? o->ch[0]->s+o->cnt : 0);}inline int lowbit(int x) {return x&-x;}void change(int x,int y) { for(int i=x;i<=m;i+=lowbit(i)) Insert(root[i],y); return ;}int query(int x,int y) { int tmp=0; for(int i=x;i;i-=lowbit(i)) tmp+=Rank(root[i],y); return tmp;}int main() { null=new Node(0,0); scanf("%d%d",&n,&m); for(int i=0;i<=m;i++) root[i]=null; for(int i=1;i<=n;i++) a[i].scan(); sort(a+1,a+1+n); for(int i=1;i<=n;i++) { if(a[i].a==a[i+1].a && a[i].b==a[i+1].b && a[i].c==a[i+1].c && i!=n) sum[i+1]+=sum[i]+1; else { int tmp=query(a[i].b,a[i].c); ans[tmp]+=sum[i]+1; } change(a[i].b,a[i].c); } for(int i=0;i<n;i++) PRintf("%d/n",ans[i]); return 0;}

上一篇：程序员优秀学习资料整理（不断更新中）

下一篇：CSDN日报20170227——《什么样的离开会让老板念念不忘》