Super Mario HDU 4417 主席树区间查询

题意

给你n个数（编号从0开始），然后查询区间内小于k的数的个数。

解题思路

这个可以使用主席树来处理，因为这个很类似查询区间内的第k小的问题。当然我们需要进行离散化，不只是那n个数，k也需要进行离散化。

详情看代码吧，有注释。

代码实现

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

using namespace std;

const int maxn=1e5+7;

struct node{

	int l, r, sum;

}t[maxn*40];

int root[maxn], cnt;

int a[maxn];

vector<int> v;

int n, m, tot;

int getid(int x) //离散化获取编号，从1开始

{

	return lower_bound(v.begin() , v.end() , x) - v.begin() +1;

}

void update(int l, int r, int pre, int &now, int pos)

{

	t[++cnt]=t[pre];

	t[cnt].sum++;

	now=cnt;

	if(l==r) return ;

	int mid=(l+r)>>1;

	if(pos<=mid)

		update(l, mid, t[pre].l, t[now].l, pos);

	else

		update(mid+1, r, t[pre].r, t[now].r, pos);

}

int query(int l, int r, int x, int y, int k1)

{

	if(r<=k1) return t[y].sum-t[x].sum; //如果第k1小大于r边界，那么这个区间内的出现的所有数都小于k1

	if(l==r) //如果到达叶子节点，那么需要判断这个点在这个区间内是否出现过。

		return t[y].sum-t[x].sum > 0 ? 1 : 0 ;

	int mid=(l+r)>>1;

	int sum=t[t[y].l].sum - t[t[x].l].sum; //计算左子树区间内的出现的数字的个数。

	if(k1<=mid)

		return query(l, mid, t[x].l, t[y].l, k1); //如果在左子树的话，需要进行递归。

	else

		return sum+query(mid+1, r, t[x].r, t[y].r, k1);//如果在右子树的话就需要加上左边区间内出现的数的个数。

}

void init() //初始化

{

	cnt=0;

	v.clear();

}

int main()

{

	int t;

	scanf("%d", &t);

	for(int ca=1; ca<=t; ca++)

	{

		init();

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

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

		{

			scanf("%d", &a[i]);

			v.push_back(a[i]);

		}

        //离散化

		sort(v.begin(), v.end() );

		v.erase( unique(v.begin() , v.end() ) ,  v.end() );

		tot=v.size(); //tot记录去重之后数的个数。

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

		{

			update(1, tot, root[i-1], root[i], getid(a[i])); //建立主席树

		}

		int x, y, k;

		printf("Case %d:\n", ca);

		for(int i=1; i<=m; i++)

		{

			scanf("%d%d%d", &x, &y, &k);

			x++; y++; //因为题目是从0开始编号的，所以对于询问我们要加1

			if(k<=0 && v[0]>0 || k<v[0]) //结果为0的情况

				printf("0\n");

			else if(k>=v[tot-1])//结果为所查区间的情况

			{

				printf("%d\n", y-x+1);

			}

			else

			{

				int tmp=getid(k);//因为我用的是lower_bound(),返回第一个大于或者等于的位置，

				if(v[tmp-1] > k)//如果不等于的话，范围需要缩小一个

					printf("%d\n", query(1, tot, root[x-1], root[y], tmp-1) );

				else printf("%d\n", query(1, tot, root[x-1], root[y], tmp) );

			}

		}

	}

	return 0;

}

巴特西

Super Mario HDU 4417 主席树区间查询

Super Mario HDU 4417 主席树区间查询

题意

解题思路

代码实现

最新文章

热门文章