BZOJ 3262(Treap+树状数组）

题面

传送门

分析

分三维考虑

对第一维，直接排序

对第二维和第三维，我们这样考虑

朴素的方法是建k棵Treap，第i棵Treap里存第二维值为k的第三维数值

每次查询一组(a,b,c),只要在1~b的Treap里查询<=c的数的个数即可

这样可以保证一定是合法的，因为排序，第一维肯定<=a，因为Treap根据值域建，第二维肯定<=b

又根据平衡树的性质，第三维肯定<=c

这样总的时间复杂度是$O(nk\log n)$，无法接受

我们考虑用树状数组的拆分方法，把一组询问拆成$\log k$组询问

第i棵Treap存储的是第二维在${[i- \rm lowbit}(i)+1,i] $之间的三元组的第三维

然后按照树状数组查找和更新的方法求出答案即可

时间复杂度$O(n \log n \log k)$

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cstdlib>

#include<stack>

#define maxn 100005

#define maxv 200005

#define maxs 5000005

#define lson tree[p].l

#define rson tree[p].r

using namespace std;

int n,k;

struct node {

	int l;

	int r;

	int val;

	int dat;

	int cnt;

	int size;

} tree[maxs];

int tot=0;

int root[maxv];

void update(int p) {

	tree[p].size=tree[lson].size+tree[rson].size+tree[p].cnt;

}

void zig(int &p) {

	int q=tree[p].l;

	tree[p].l=tree[q].r;

	tree[q].r=p;

	p=q;

	update(tree[p].r);

	update(p);

}

void zag(int &p) {

	int q=tree[p].r;

	tree[p].r=tree[q].l;

	tree[q].l=p;

	p=q;

	update(tree[p].l);

	update(p);

}

int New(int val) {

	tree[++tot].val=val;

	tree[tot].dat=rand();

	tree[tot].cnt=1;

	tree[tot].size=1;

	return tot;

}

void insert(int &p,int val) {

	if(p==0) {

		p=New(val);

		return;

	}

	if(val==tree[p].val) {

		tree[p].cnt++;

		update(p);

		return;

	}

	if(val<tree[p].val) {

		insert(lson,val);

		if(tree[lson].dat>tree[p].dat) zig(p);

	} else {

		insert(rson,val);

		if(tree[rson].dat>tree[p].dat) zag(p);

	}

	update(p);

}

int get_rank_by_val(int p,int val) {

	if(p==0) return 0;

	if(val==tree[p].val) {

		return tree[lson].size+tree[p].cnt;

	}

	if(val<tree[p].val) {

		return get_rank_by_val(lson,val);

	}

	return get_rank_by_val(rson,val)+tree[lson].size+tree[p].cnt;

}

inline int lowbit(int x) {

	return x&-x;

}

void update(int x,int v){

	while(x<=k){ //注意，树状数组是根据值域建的，所以范围是k，不要写成x<=n

//		printf("	tree %d, update %d\n",x,v);

		insert(root[x],v);

		x+=lowbit(x);

	}

}

int query(int x,int v){

	int level=0;

	while(x){

//		printf("	tree %d, query %d\n",x,v );

		level+=get_rank_by_val(root[x],v);

		x-=lowbit(x);

	}

	return level;

}

struct flower{

	int s;

	int c;

	int m;

	friend bool operator == (flower a,flower b){

		return a.s==b.s&&a.c==b.c&&a.m==b.m;

	}

	friend bool operator < (flower a,flower b){

		if(a.s==b.s){

			if(a.c==b.c) return a.m<b.m;

			else return a.c<b.c;

		}else{

			return a.s<b.s;

		}

	}

}a[maxn];

int level[maxn];

int cnt[maxn];

stack<int>s;

int main() {

	scanf("%d %d",&n,&k);

	for(int i=1;i<=n;i++){

		scanf("%d %d %d",&a[i].s,&a[i].c,&a[i].m);

	}

	sort(a+1,a+1+n);

	for(int i=1;i<=n;i++){

		if(a[i]==a[i+1]) s.push(i);

		else{

			level[i]=query(a[i].c,a[i].m);

			while(!s.empty()){

				level[s.top()]=level[i];

				s.pop();

			}

		}

		update(a[i].c,a[i].m);

	}

	for(int i=1;i<=n;i++){

		cnt[level[i]]++;

	}

	for(int i=0;i<=n-1;i++){

		printf("%d\n",cnt[i]);

	}

}

巴特西

BZOJ 3262(Treap+树状数组）

题面

分析

代码

最新文章

热门文章