BZOJ3262陌上花开 CDQ分治_BIT+Treap

三个属性, 第一个属性用cdq分治处理, 以第一个属性为关键字从小到大排序, 那么考虑一朵花的等级, 只需考虑排在其前面的花的其他属性(特殊情况是有相同的花,根据题意,对一段相同的花,以排在最后的一朵花的答案为准), 第二三维可以用树状数组加Treap解决, 以每朵花第二属性数值作为位置(因为最大属性k < 2e5, 可以不用离散化, 直接用属性的数值对应树状数组中的下标), 树状数组的每个节点建一颗Treap, 这颗Treap里存的是相应区间里的花的第三个属性, 询问时类似于树状数组求前缀和, 依次将询问的花的位置的前面这一段分成不超过logk棵Treap对应的区间, 在这些区间里可以找出, 由于是以第二属性为位置插入到树状数组里的, 保证前面一段区间的第二属性都是不超过我们询问的花的第二属性, 只要在这不超过logk棵Treap里找出第三属性不超过询问的花的数量, 就是三个属性均不超过询问的花的三个属性的花的数量

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn = 2e5 + 7, maxk = 2e5 + 7, maxnd = 1e6 + 7;

void readin(int &ret) {
    ret = 0; int f = 1; char ch = getchar();
    while(ch < ‘0‘ || ch > ‘9‘) {if(ch == ‘-‘) f = -1; ch = getchar();}
    while(ch >= ‘0‘ && ch <= ‘9‘) ret *= 10, ret += ch - ‘0‘, ch = getchar();
    ret *= f;
}

struct flower {
	int s, c, m, id, ans;
	void read() {
		readin(s); readin(c); readin(m);
	}
} f[maxn];
bool cmp(const flower& a, const flower& b) {
	return a.s < b.s || (a.s == b.s && a.c < b.c) || (a.s == b.s && a.c == b.c && a.m < b.m);
}

bool ssame(const flower& a, const flower& b) {
	return a.s == b.s && a.c == b.c && a.m == b.m;
}
int n, k, siz, ans[maxn], root[maxn], sz[maxnd], val[maxnd], rnd[maxnd], cnt[maxnd], c[maxnd][2];
void update(int k) {
	sz[k] = sz[c[k][0]] + sz[c[k][1]] + cnt[k];
}
void rotate(int &k, int ch) {
	int t = c[k][ch]; c[k][ch] = c[t][ch ^ 1]; c[t][ch ^ 1] = k;
	sz[t] = sz[k]; update(k); k = t;
}
void insert(int &k, int x) {
	if(!k) {
		val[k = ++siz] = x;
		rnd[k] = rand();
		sz[k] = cnt[k] = 1;
		c[k][0] = c[k][1] = 0;
	} else if(val[k] == x) sz[k]++, cnt[k]++;
	else {
		sz[k]++;
		int d = val[k] < x;
		insert(c[k][d], x);
		if(rnd[c[k][d]] < rnd[k]) rotate(k, d);
	}
}
int find(int k, int x) {
	if(!k) return 0;
	if(val[k] == x) return sz[c[k][0]] + cnt[k];
	if(val[k] > x) return find(c[k][0], x);
	return sz[c[k][0]] + cnt[k] + find(c[k][1], x);
} //find(k, x)找出节点k为根的子树中, 权值不大于x的节点数量
#define lowbit(x) (x&-x)
void ins(int pos, int x) {
	while(pos <= k) {
		insert(root[pos], x);
		pos += lowbit(pos);
	}
}
int query(int pos, int x) {
	int ret = 0;
	while(pos > 0) {
		ret += find(root[pos], x);
		pos -= lowbit(pos);
	}
	return ret;
}

int top, stk[maxn], num[maxn];
int main() {
	readin(n); readin(k);
	for(int i = 1; i <= n; i++) f[i].read();
	sort(f + 1, f + n + 1, cmp);
	top = 0;
	for(int i = 1; i <= n; i++) {
		if(ssame(f[i], f[i + 1])) stk[++top] = i;//如果有相同的花, 先存到数组里, 直到处理了最后一朵这种花再更新前面的答案
		else {
			f[i].ans = query(f[i].c, f[i].m);
			while(top) f[stk[top--]].ans = f[i].ans;
		}
		ins(f[i].c, f[i].m);//询问了这朵花后再将这朵花插入树状数组中
	}
	for(int i = 1; i <= n; i++) num[f[i].ans]++;
	for(int i = 0; i <= n - 1; i++) printf("%d\n", num[i]);
	return 0;
}

  

时间: 02-19

BZOJ3262陌上花开 CDQ分治_BIT+Treap的相关文章

BZOJ3262/洛谷P3810 陌上花开 CDQ分治 三维偏序 树状数组

原文链接http://www.cnblogs.com/zhouzhendong/p/8672131.html 题目传送门 - BZOJ3262 题目传送门 - 落谷P3810 题意 有$n$个元素,第$i$个元素有$a_i$.$b_i$.$c_i$三个属性,设$f(i)$表示满足$a_j\leq a_i$且$b_j\leq b_i$且$c_j\leq c_i$的$j$的数量.对于$d\in [0,n)$,求$f(i)=d$的数量. $n\leq 100000,max\{a_i,b_i,c_i|i

BZOJ 3262: 陌上花开 [CDQ分治 三维偏序]

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行,每

BZOJ 3262: 陌上花开 cdq分治 树状数组

https://www.lydsy.com/JudgeOnline/problem.php?id=3262 cdq分治板子题,一维排序,一维分治(cdq里的队列),一维数据结构(树状数组). 学dp优化前来复习--以前好像写过这道题但是没写博客啊--在校oj上写的题都没怎么写博客,追悔莫及 1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #

luogu3810 陌上花开 (cdq分治)

求三维偏序 设三维为a,b,c.先对a排序,这样i的偏序就只能<i. 然而排序的时候需要三个维度都判断一遍,最后还要去重,不然会出现实际应该记答案的数出现在它后面的情况. (排序用的函数里不要写类似于<=之类的东西啊..会出奇奇怪怪的问题的(RE)) 然后分治来做,我们在做区间[l,r]的时候,先去做[l,m]和[m+1,r] 之后左区间[l,m],右区间[m+1,r]都已经按照b排好序了,而且左右两区间内部的答案已经统计过了,所以现在只要考虑左区间中满足(右区间的数)的数量就好了. 那么就也

bzoj 3262: 陌上花开 -- CDQ分治

3262: 陌上花开 Time Limit: 20 Sec  Memory Limit: 256 MB Description 有n朵花,每朵花有三个属性:花形(s).颜色(c).气味(m),又三个整数表示.现要对每朵花评级,一朵花的级别是它拥有的美丽能超过的花的数量.定义一朵花A比另一朵花B要美丽,当且仅当Sa>=Sb,Ca>=Cb,Ma>=Mb.显然,两朵花可能有同样的属性.需要统计出评出每个等级的花的数量. Input 第一行为N,K (1 <= N <= 100,00

【BZOJ3262】陌上花开(CDQ分治)

[BZOJ3262]陌上花开(CDQ分治) 题解 原来放过这道题目,题面在这里 树套树的做法也请点上面 这回用CDQ分治做的 其实也很简单, 对于第一维排序之后 显然只有前面的对后面的才会产生贡献 那么,使用CDQ分治 先分,每次递归子问题 合并的时候每次考虑前面的对于后面的贡献 最后统计一下答案 如果在清空树状数组的时候用了memset会TLE #include<iostream> #include<cstdio> #include<cstdlib> #include

[CDQ分治][Treap][树状数组]Theresa与数据结构

Description 这是个复杂的世界.人类社会,自然界,还有地球之外的银河--每一天日出日落,人来人往,步履匆匆.究竟是为什么呢?那支配着一切的至高无上的法则又是否存在呢?Theresa知道,这个问题并不是一朝一夕就可以解答的,只有在仔细.深入的观察和思考以后,才有可能将所有支离破碎的线索联系起来,从而隐约窥见真实的答案.于是,Theresa经常思考生活中遇到的大大小小的问题.为什么港台出版的书籍里印刷的汉字她一个也不认识呢?为什么隔夜的白开水中富含一氧化二氢呢?为什么每年都有一段时间Gma

洛谷 P3810 【模板】三维偏序(陌上花开) (cdq分治模板)

在solve(L,R)中,需要先分治solve两个子区间,再计算左边区间修改对右边区间询问的贡献. 注意,计算额外的贡献时,两子区间各自内部的顺序变得不再重要(不管怎么样左边区间的都发生在右边之前),于是就少了一维 https://www.lydsy.com/JudgeOnline/problem.php?id=3262 https://www.luogu.org/problemnew/show/P3810 此题每个操作既是修改又是查询 对于此题,先按一维排序,在solve(L,R)中先solv

P3810 【模板】三维偏序(陌上花开)(cdq分治)

思路 看到这种偏序类的题目,而且不要求强制在线,可以立刻想到cdq分治 注意这题有一个问题,就是询问的是小于等于而不是小于,如果相等的话两个元素会相互贡献,而cdq的特点是右区间不能对左边有影响,所以要先去重,再然后就是板子 代码 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; int n,maxn; namespace BIT{ int bit[200100]