程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> UVa 11235 Frequent values / RMQ or 線段樹

UVa 11235 Frequent values / RMQ or 線段樹

編輯：C++入門知識

連續相同的數為一段 cnt[i] 為第i段出現次數

對於每次詢問l,r

判斷l,r,分別屬於哪一段比如說是 x,y 那麼求x+1 到y-1段的RMQ

另外x,y分別還有一部分別忘記

RMQ 線段樹都可以解

RMQ

#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 100010;
int a[maxn];//輸入的數 連續相同的分成一段 
int value[maxn];//每一段的值 
int cnt[maxn];//每一段的個數 
int num[maxn];//每個數所在哪一段 
int l[maxn];//每個數在段的左界限 
int r[maxn];//每個數在段數右界限
int dp[maxn][50];
void RMQ_init(int n)
{
	for(int i = 1; i <= n; i++)
		dp[i][0] = cnt[i];
	for(int j = 1; (1< mp;
		map  ::iterator it;
		for(i = 1; i <= n; i++)
		{
			scanf("%d", &a[i]);
			mp[a[i]]++;
		}
		int sum = 0;
		for(it = mp.begin(), i = 1, j = 1; it != mp.end(); it++, i++)
		{
			sum += it -> second;
			while(j <= sum)
			{
				l[j] = sum - it -> second + 1;
				r[j] = sum;
				num[j] = i;
				j++;
			}
			value[i] = it -> first;
			cnt[i] = it -> second;
		}
		//n = i;
		int len = i - 1;
		//for(i = 1; i <= n; i++)
		//	printf("%d %d %d\n",num[i], l[i], r[i]);
		//for(i = 1; i <= len; i++)
		//	printf("%d %d\n",value[i], cnt[i]);
		RMQ_init(len);
		while(m--)
		{
			int x, y;
			scanf("%d %d", &x, &y);
			if(num[x] == num[y])
				printf("%d\n", y-x+1);
			else
			{
				int s1 = r[x] - x + 1;
				int s2 = y - l[y] + 1;
				s1 = max(s1, s2);
				int s3 = 0;
				if(num[y] - 1 >= num[x] + 1)
					s3 = RMQ(num[x]+1, num[y]-1);
				printf("%d\n",max(s1, s3));
			}
		}
	}
	return 0;
}