求调两道站外题（可能不是站外题）

T1

A 喜欢研究「完美序列」：一段连续的序列，满足序列中的数互不相同。A 想知道区间[L,R]之间最长的完美序列长度。

第一行两个整数N,M，N表示序列长度，元素编号为0到N−1，M表示询问的次数；

第二行N个整数，第i个数表示序列元素a[i].

接下来M行每行两个整数L,R，表示 A 询问的区间。

输出M行，每行一个整数对应询问区间内的完美序列的最长长度。

CPP

#include <iostream>
using namespace std;

int a[200010], f[200010][30], L[200010], pos[2000010];

int main()
{
	int n, m;
	cin >> n >> m;
	L[0] = 1;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		a[i] += 1e6;
		L[i] = max(L[i - 1], pos[a[i]] + 1);
		pos[a[i]] = i;
	}
	for (int k = 1; k <= 20; k++)
	{
		for (int i = 1; i + (1 << k) - 1 <= n; i++)
		{
			f[i][k] = max(f[i][k - 1], f[i + (1 << k - 1)][k - 1]);
		}
	}
	for (int i = 1, l, r; i <= m; i++)
	{
		cin >> l >> r;
		l++, r++;
		int pos = lower_bound(L + l, L + r + 1, l) - L;
		if (pos >= r)
		{
			cout << 0 << endl;
			continue;
		}
		int k = __lg(r - pos + 1);
		cout << max(max(f[pos][k], f[r - (1 << k) + 1][k]), pos - l) << endl;
	}
	return 0;
}

T2 给出一个长度为n(1<=n<=10^5) 的序列和q(1<=q<=3∗10^5)个询问,每个询问输出一行,询问gcd(a[i],a[i + 1]……,a[j])=x的(i,j) 的对数。

第1行一个正整数n，表示序列的元素个数。

第2行n个正整数，表示输入的序列，保证序列中每个数字都在int范围内。

第3行一个正整数q，表示询问的个数。

第4到q+3行，每行一个正整数，表示每次询问的gcd的值。

对于每次询问，输出单独的一行表示这次询问的答案。

CPP

#include <iostream>
#include <map>
#include <algorithm>
using namespace std;

int f[100010][30], cnt[100010];

int qu(int l, int r)
{
	int k = __lg(r - l + 1);
	return __gcd(f[l][k], f[r - (1 << k) + 1][k]);
}

int main()
{
	int n, q;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> f[i][0];
	}
	for (int k = 1; k <= 20; k++)
	{
		for (int i = 1; i + (1 << k) - 1 <= n; i++)
		{
			f[i][k] = __gcd(f[i][k - 1], f[i + (1 << k - 1)][k - 1]);
		}
	}
	for (int i = 1; i <= n; i++)
	{
		int L = i;
		while (L <= n)
		{
			int x = qu(i, L), l = L, r = n, R = L;
			while (l <= r)
			{
				int m = (l + r) / 2;
				if (qu(i, m) == x)  R = m, l = m + 1;
				else  r = m - 1;
			}
			cnt[x] += R - L + 1;
			L = R + 1;
		}
	}
	cin >> q;
	for (int i = 1, x; i <= q; i++)
	{
		cin >> x;
		cout << cnt[x] << endl;
	}
	return 0;
}

求调两道站外题（可能不是站外题）

讨论操作

T1

回复

相关推荐

求调两道站外题（可能不是站外题）