BZOJ 3262(树套树)

2024-08-23 14:38
文章标签 bzoj 3262 树套

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

bzoj3262】陌上花开

Description

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

Input

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

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

Output

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

Sample Input

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

Sample Output

3
1
3
0
1
0
1
0
0
1

HINT

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(树套树)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1099670

相关文章

【BZOJ】1324 Exca王者之剑 最大权独立集

传送门:【BZOJ】1324  Exca王者之剑 题目分析:赤裸裸的最大权独立集。。。最小割解决 代码如下: #include <cstdio>#include <vector>#include <cstring>#include <algorithm>using namespace std ;#define REP( i , a , b ) for ( int

【BZOJ】1026: [SCOI2009]windy数 数位DP

传送门:【BZOJ】1026: [SCOI2009]windy数 题目分析:数位DP水题。 代码如下: #include <stdio.h>#include <cstring>#include <algorithm>#define rep( i , a , b ) for ( int i = a ; i < b ; ++ i )#define For( i ,

【BZOJ】2152: 聪聪可可 点分治

传送门:【BZOJ】2152: 聪聪可可 题目分析:记录权值和%3的路径的个数。。。然后去重。。没了。。 代码如下: #include <vector>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std ;typedef lo

BZOJ 2440 2301 莫比乌斯应用

http://www.lydsy.com/JudgeOnline/problem.php?id=2440 Description 小 X 自幼就很喜欢数。但奇怪的是,他十分讨厌完全平方数。他觉得这些 数看起来很令人难受。由此,他也讨厌所有是完全平方数的正整数倍的数。然而 这丝毫不影响他对其他数的热爱。  这天是小X的生日,小 W 想送一个数给他作为生日礼物。当然他不能送一 个小X讨厌

BZOJ 3732: Network(最小生成树+倍增)

题目链接 题意:给出一个图,每个询问的格式是:A B,表示询问从A点走到B点的所有路径中,最长的边最小值是多少 很明显最终查询的边一定是在最小生成树里面的,先跑出最小生成树,然后,可以树链剖分,也可以使用倍增来计算 #include<bits/stdc++.h>using namespace std;#define cl(a,b) memset(a,b,sizeof(a))#define

BZOJ 2038 小Z的袜子(hose) (莫队离线)

题目地址:BZOJ 2038 裸的莫队算法。 代码如下: #include <iostream>#include <string.h>#include <math.h>#include <queue>#include <algorithm>#include <stdlib.h>#include <map>#include <set>#include <stdio.h>#in

BZOJ 2152 聪聪可可 (树上点分治)

题目地址:BZOJ 2152 找有多少对权值和为3的倍数的点。最简单的点分治。 代码如下: #include <iostream>#include <string.h>#include <math.h>#include <queue>#include <algorithm>#include <stdlib.h>#include <map>#include <set>#incl

poj 3262贪心

看的大神的证明: 贪心 > 当前最优,因为每一次搬运之后剩下的问题和原问题一样,只是规模变小了,故如果每次选出当前最优的解来进行选取,则累计起来的解也是最优的.> 所以这是一道贪心题.> 选择策略,> 1 在二个中间选择之中,能根据time/eat小的那个为最优解> 证明:> 二个羊中 A,B,属性分别为分别为eatA,timeA,eatB,timeB> 选A的时候损失tim

BZOJ 3530 数数【AC自动机+数位dp】

[Sdoi2014]数数 简单数位dp+简单AC自动机 反正数位DP是队友写的 AC自动机要记录两个值,一个是是否为一个串的结束,即不合法状态,一个是前缀零的情况。 // whn6325689// Mr.Phoebe// http://blog.csdn.net/u013007900#include <algorithm>#include <iostr

BZOJ 3531 旅行【树链剖分】

[Sdoi2014] 简单的树链剖分 以每个信仰应该建一个线段树,空间复杂度为 O(5×1010) O(5\times 10^{10}) 因此会爆空间,所以需要动态申请空间。 // whn6325689// Mr.Phoebe// http://blog.csdn.net/u013007900#include <algorithm>#include <