CD from Codeforces Round #703 (Div. 2)

C. Guessing the Greatest

交互题，给一个permutation，每次可以查询一个区间的第二大值，让你在20次以内找到permutation中的最大值。

做法：只要每次查询都包含全区间的第二大值，就能二分判断最大值在不在查询的区间里了

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define vll vector<ll>
#define vpll vector<pll>
#define fastio ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
double pi = acos(-1);
const double eps = 1e-9;
const int inf = 1e9 + 7;
const ll lnf = 1e18 + 7;
const int maxn = 1e5 + 10;
ll mod = 1e9 + 7;

int main()
{
	fastio;
	int n;
	cin >> n;
	int sec;
	cout << "? " << 1 << " " << n << endl;
	cout.flush();
	cin >> sec;
	int l, r, flag = 0;
	int tmp;
	if (sec == 1)
		l = 2, r = n, flag = 1;
	else if (sec == n)
		l = 1, r = n - 1, flag = 0;
	else
	{
		cout << "? " << 1 << " " << sec << endl;
		cout.flush();
		cin >> tmp;
		if (tmp == sec)
			l = 1, r = sec - 1, flag = 0;
		else
			l = sec + 1, r = n, flag = 1;
	}
	int ans = -1;
	while (l <= r)
	{
		//cout << l << " " << r << endl;
		int mid = l + r >> 1;
		if (flag)
		{
			cout << "? " << sec << " " << mid << endl;
			cout.flush();
			cin >> tmp;
			if (tmp == sec)
			{
				ans = mid;
				r = mid - 1;
			}
			else l = mid + 1;
		}
		else
		{
			cout << "? " << mid << " " << sec << endl;
			cout.flush();
			cin >> tmp;
			if (tmp == sec)
			{
				ans = mid;
				l = mid + 1;
			}
			else
				r = mid - 1;
		}
	}
	cout << "! " << ans << endl;
	return 0;

}

D. Max Median

题意：让你找长度最少为k的区间中中位数的最大值。

二分一个答案x，然后把小于x的数标记为-1，大于等于的标记为+1，跑一个前缀和pre[i]，并在pre[i-k]处记录前缀最小值MIN，这样就能保证区间长度至少为k。

然后用pre与MIN做差，如果大于0则二分的这个数可以作为一个答案（不一定在a中存在），最终二分的值必然在a中存在，因为二分到的是一个边界。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define vll vector<ll>
#define vpll vector<pll>
#define fastio ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
double pi = acos(-1);
const double eps = 1e-9;
const int inf = 1e9 + 7;
const ll lnf = 1e18 + 7;
const int maxn = 2e5 + 10;
ll mod = 1e9 + 7;

int n, k;

int a[maxn];

int check(int x)
{
	vector<int>pre(n + 2, 0);
	int MIN = inf;
	for (int i = 1; i <= n; i++)
	{
		pre[i] = pre[i - 1] + (a[i] >= x ? 1 : -1);
		if (i >= k)
			MIN = min(MIN, pre[i - k]);
		if (pre[i] - MIN > 0)return 1;
	}
	return 0;
}

int main()
{
	fastio;
	cin >> n >> k;
	int MAX = 0;
	for (int i = 1; i <= n; i++)cin >> a[i], MAX = max(MAX, a[i]);
	int l = 1, r = MAX, ans = -1;
	while (l <= r)
	{
		int mid = l + r >> 1;
		if (check(mid))
		{
			ans = mid;
			l = mid + 1;
		}
		else
			r = mid - 1;
	}
	cout << ans << endl;
	return 0;

}