首页 > 代码库 > POJ3368 Frequent values 线段树

POJ3368 Frequent values 线段树

2024-07-14 18:06:20   222人阅读

        N个数为非递减顺序，给定范围l,r，求[l,r]区间内数字出现频率最高的次数。

        可以用线段树来做。先说查询，我们设节点P对应的区间为[a, b]，左孩子节点为p1,右孩子节点为p2,那么 P也许不等于 max(p1 , p2)，原因是如果p1中频率较低的某个数与p2中出现频率较低的某个数是同一个数，并且两者出现次数加起来大于max(p1, p2)，但是，题目说N个数为非递减顺序排列，所以这个可能只会发生在p1的右端和p2的左端对应的数是同一个数，因此，我们还要处理这第三个可能。

        查询的问题解决，现在剩下的就是建立这棵线段树，这比较容易，只是在从叶子节点向根节点更新的时候有点特殊，我们只要知道当前更新的元素以及它在当前节点对应的区间内出现的次数即可，然后以最大值更新该节点，这一步，需要进行一个预处理：依次扫描N个数，对每个数出现的开始位置和结束位置进行记录即可。

#include <stdio.h>
#include <vector>
#include <math.h>
#include <string.h>
#include <string>
#include <iostream>
#include <queue>
#include <list>
#include <algorithm>
#include <stack>
#include <map>
#include <time.h>
using namespace std;


inline void QuadMemSet(void* dst, int iSize, int value)
{
	iSize = iSize / 4;
	int* newDst = (int*) dst;
#ifdef WIN32
	__asm
	{
		mov edi, dst 
		mov ecx, iSize
		mov eax, value  
		rep stosd
	}
#else
	for (int i = 0; i < iSize;i++)
	{
		newDst[i] = value;
	
	}
#endif
}
#define MAXN 100001
#define MAXVALUE  200001
int values[MAXN];
int ranges[MAXVALUE][2];
int St[265000];

template<class TYPE>
void UpdateValue(TYPE st[],int i, TYPE value, int N)
{
	int a = i;
	int b = i;
	i += N - 1;
	st[i] = 1;
	int left = ranges[value][0];
	int right = ranges[value][1];

	int tmp;
	while (i > 0)
	{
		tmp = (i - 1) / 2;
		if (tmp * 2 + 1 == i) //左孩子
		{
			b += (b - a) + 1;
		}
		else
		{
			a -= (b - a) + 1;
		}
		int count = 0;
		int tmpa = max(a, left);
		int tmpb = min(b, right);
		count = tmpb - tmpa + 1 > 0 ? tmpb - tmpa + 1 : 0;
		i = tmp;
		st[i] = max(st[i], count);
	}
}

template<class TYPE>
TYPE QueryST(TYPE st[], int a, int b, int l, int r, int k)
{
	if (l > b || a > r)
	{
		return 0;
	}
	if (l >= a && b >= r)
	{
		return st[k];
	}
	else
	{
		TYPE value1 = QueryST(st, a, b, l, (r + l) / 2, k * 2 + 1);
		TYPE value2 = QueryST(st, a, b, (r + l) / 2 + 1, r, k * 2 + 2);
		TYPE value3 = 0;
		if (values[(r + l) / 2] == values[(r + l) / 2 + 1])
		{
			int start = ranges[values[(r + l) / 2]][0];
			int end = ranges[values[(r + l) / 2]][1];
			start = max(a, start);
			end = min(b, end);
			value3 = end - start + 1;
		}
		
		return max(max(value1, value2), value3);
		
	}
}

int main()
{
#ifdef _DEBUG
	freopen("e:\\in.txt", "r", stdin);
#endif
	int n, q;
	while (scanf("%d", &n) != EOF)
	{
		if (n == 0)
		{
			break;
		}
		scanf("%d",&q);
		QuadMemSet(ranges, sizeof(ranges), -1);
		QuadMemSet(St, sizeof(St), 0);
		int lastvalue = http://www.mamicode.com/-1;>


联系
我们