Educational Codeforces Round 80

D. Minimax Problem

题意：
给你n个长度为m的数组，每两个数组通过同列取max可得一个新的数组v，找出两个数组使得v的最小值尽可能大。
分析:
两两枚举数组肯定超时，考虑用二分的思想。二分最小值的最大值val。然后通过val将数组二进制化，>=val的位置设为1，否则为0.这样一来，n个数组便化成了若干个二进制数（<=(1 << m) - 1）,从0到((1 << m) - 1)两两枚举a, b， 如果a | b == （1 << m） - 1，那么就说明真实的最大值一定不小于val，之后继续二分即可。
注意二分的条件判断是l <= r， 而且l，r一定会变化，不会产生死循环。
代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e5 + 10;
int v[maxn][10];
int a, b;
int n, m;

bool judge(int val)
{
	map<int, int> ma;
	for (int i = 0; i < n; i++)
	{
		int res = 0;
		for (int j = 0; j < m; j++)
			if (v[i][j] >= val)
				res ^= (1 << j);
		ma[res] = i;
	}
	if (ma.count((1 << m) - 1))
	{
		a = b = ma[(1 << m) - 1];
		return true;
	}
	for (int i = 0; i < (1 << m); i++)
		for (int j = i; j < (1 << m); j++)
			if (ma.count(i) && ma.count(j) && (i | j) == (1 << m) - 1)
			{
				a = ma[i], b = ma[j];
				return true;
			}
	return false;

}

int main()
{
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			scanf("%d", &v[i][j]);
	int l = 1, r = 1e9;
	while (l <= r)
	{
		int mid = (l + r) >> 1;
		if (judge(mid))
			l = mid + 1;
		else r = mid - 1;
	}
	cout << a + 1 << " " << b + 1 << endl;
}

E. Messenger Simulator

题意:
一开始有一个初始顺序的排列[1,n]，一共有m次操作，每次将数ai从序列中取出，放到最开头的位置生成一个新的排列。
求问在所有过程中每一个数最小的下标位置和最大的下标位置。
分析：
http://blog.leanote.com/post/icontofig/b546d6e423ff
代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e5 + 10;
int v[maxn];
ll tree1[maxn];
ll tree2[maxn];
ll front[maxn], rear[maxn];
int lastpos[maxn];
int n, m;

ll lowbit(int x)
{
	return x & (-x);
}

void add1(int pos, int val)
{
	for (int i = pos; i <= n; i += lowbit(i))
		tree1[i] += val;
}

ll sum1(int pos)
{
	ll sum = 0;
	for (int i = pos; i >= 1; i -= lowbit(i))
		sum += tree1[i];
	return sum;
}

void add2(int pos, int val)
{
	for (int i = pos; i <= m; i += lowbit(i))
		tree2[i] += val;
}

ll sum2(int pos)
{
	ll sum = 0;
	for (int i = pos; i >= 1; i -= lowbit(i))
		sum += tree2[i];
	return sum;
}


int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		front[i] = rear[i] = i;
	for (int i = 1; i <= m; i++)
		scanf("%d", v + i), front[v[i]] = 1;
	for (int i = 1; i <= m; i++)
	{
		int now = v[i];
		if (!lastpos[now])
		{
			add1(now, 1);
			add2(i, 1);
			lastpos[now] = i;
			rear[now] += sum1(n) - sum1(now);
		}
		else
		{
			add2(lastpos[now], -1);
			add2(i, 1);
			rear[now] = max(rear[now], sum2(i - 1) - sum2(lastpos[now]) + 1);
			lastpos[now] = i;
		}
	}
	//cout << rear[1] << endl;
	for(int i = 1; i <= n; i++)
		if (!lastpos[i])
			rear[i] += sum1(n) - sum1(i);
		else
			rear[i] = max(rear[i], sum2(m) - sum2(lastpos[i]) + 1);
	
	for (int i = 1; i <= n; i++)
		printf("%lld %lld\n", front[i], rear[i]);
}