BZOJ 3262（树套树）

本文主要是介绍BZOJ 3262（树套树），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【bzoj3262】陌上花开

有n朵花，每朵花有三个属性：花形(s)、颜色(c)、气味(m)，又三个整数表示。现要对每朵花评级，一朵花的级别是它拥有的美丽能超过的花的数量。定义一朵花A比另一朵花B要美丽，当且仅当Sa>=Sb,Ca>=Cb,Ma>=Mb。显然，两朵花可能有同样的属性。需要统计出评出每个等级的花的数量。

第一行为N,K (1 <= N <= 100,000, 1 <= K<= 200,000 ), 分别表示花的数量和最大属性值。

以下N行，每行三个整数si, ci, mi (1 <= si, ci, mi <= K)，表示第i朵花的属性

包含N行，分别表示评级为0...N-1的每级花的数量。

10 3
3 3 3
2 3 3
2 3 1
3 1 1
3 1 2
1 3 1
1 1 2
1 2 2
1 3 2
1 2 1

3
1
3
0
1
0
1
0
0
1

1 <= N <= 100,000, 1 <= K <= 200,000

一维按x值从小到大排序，二维按y值建立树状数组，三维对每个root[y]构建Treap

没有BZOJ 的VIP账号 不能提交 不知道能不能AC，大致思路是正确的。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 200009
#define lowbit(x) (x&-x)
int n,k;
struct Num {int x,y,z;Num(){}Num(int _x,int _y,int _z) {x = _x; y = _y; z = _z;}friend bool operator < (Num n1,Num n2) {if(n1.x != n2.x) return n1.x < n2.x;if(n1.y != n2.y) return n1.y < n2.y;return n1.z < n2.z;}
}num[N];
struct Node {Node *ch[2];int value,siz,rank;Node(){ ch[0] = ch[1] = NULL; }Node(int v,int r) {ch[0] = ch[1] = NULL;value = v; rank = r; siz = 1;}int lr_ch(Node *(&node)){ return ch[1]==node; }void link_ch(Node *(&node),int d) {ch[d] = node;}void push_up() {siz = 1;if(ch[0]!=NULL) siz += ch[0]->siz;if(ch[1]!=NULL) siz += ch[1]->siz;}
}*root[N];
int ans[N];
void rotate(Node *(&node),int d) {Node *ch = node -> ch[d^1];node -> link_ch(ch->ch[d],d^1);node -> push_up();ch -> link_ch(node,d);ch -> push_up();node = ch;
}
void insert(Node *(&node),int v) {if(node == NULL) {node = new Node(v,rand());return;}int d = (v >= node->value);insert(node->ch[d],v);node->push_up();if(node->ch[d]->rank > node->rank)rotate(node,d^1);
}
int getRank(Node *(&node),int v) {if(node == NULL)  return 0;if(v < node->value) return getRank(node->ch[0],v);else {int t = (node->ch[0]==NULL?0:node->ch[0]->siz);return t + 1 + getRank(node->ch[1],v);}
}
void add(int y,int z) {for(int i = y;i<=k;i+=lowbit(i))insert(root[i]->ch[1],z);
}
int getSum(int y,int z) {int sum = 0;for(int i = y;i>=1;i-=lowbit(i))sum += getRank(root[i]->ch[1],z);return sum;
}
void solve() {int tem = 0;for(int i = 1;i<=n;i++) {int x = num[i].x, y = num[i].y, z = num[i].z;if(n!=i&&num[i+1].x==x&&num[i+1].y==y&&num[i+1].z==z)  tem++;else {int sum = getSum(y,z);ans[sum] = ans[sum] + tem + 1;tem = 0;}add(y,z);}
}
void init() {for(int i = 0;i<=n;i++) {delete root[i]; root[i] = NULL;root[i] = new Node();}memset(ans,0,sizeof(ans));
}
void getData() {int x,y,z;for(int i = 1;i<=n;i++) {scanf("%d%d%d",&x,&y,&z);num[i] = Num(x,y,z);}sort(num+1,num+1+n);
}
void outData(){for(int i = 0;i<n;i++) printf("%d\n",ans[i]);
}
int main() {//freopen("Test.txt","r",stdin);while(~scanf("%d%d",&n,&k)) {init();getData();solve();outData();}return 0;
}

这篇关于BZOJ 3262（树套树）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---