比赛-CioCio学长的训练赛 (18 Aug, 2018)

1.) wjj 的子集序列

暴力二进制枚举子集打表，然后可以发现答案就是最大值。根据公式推一波也行吧……

#include <cstdio>
#include <stack>
#include <ctype.h>

using namespace std;

typedef long long ll;

template<typename T>
void rd(T &num)
{
	char tt;
	bool flag = 0;
	while (!isdigit(tt = getchar()) && tt != '-');
	if (tt == '-') num = 0, flag = 1;
	else num = tt - '0';
	while (isdigit(tt = getchar()))
		num = num * 10 + tt - '0';
	if (flag) num = -num;
	return;
}

template<typename T>
void pt(T num)
{
	if (num < 0) putchar('-'), num = -num;
	stack<char> SSS;
	do SSS.push(num % 10 + '0');
	while (num /= 10);
	while (!SSS.empty())
		putchar(SSS.top()), SSS.pop();;
	putchar('
');
	return;
}

ll ans;

int main()
{
	freopen("subset.in", "r", stdin);
	freopen("subset.out", "w", stdout);
	
	int N;
	rd(N);
	for (int i = 1; i <= N; ++i) {
		ll t;
		rd(t);
		if (i == 1 || ans < t) ans = t;
	}
	pt(ans);
	return 0;
}

2.) wjj 的排列序列

没有限制条件时，显然最优排列是一个单调下降的排列。比如 $ {5, 4, 3, 2, 1} $ 。只有一个限制条件时，比如要求 (5) 在 (2) 之后，最优排列是 $ {4, 3, 2, 5, 1} $ 。分析一下可以发现应该尽量把较大的数放在前面，当然是在保证满足限制条件的情况下。简单反证一下，如果不尽量把较大的放在前面，有的数字就会被前面较小的数“压制”，前缀最小值就会变小，所以不行。为了满足限制条件，可以写一个类似 Top-sort 的东西。

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <stack>
#include <ctype.h>

using namespace std;

template<typename T>
void rd(T &num)
{
	char tt;
	bool flag = 0;
	while (!isdigit(tt = getchar()) && tt != '-');
	if (tt == '-') num = 0, flag = 1;
	else num = tt - '0';
	while (isdigit(tt = getchar()))
		num = num * 10 + tt - '0';
	if (flag) num = -num;
	return;
}

template<typename T>
void pt(T num)
{
	if (num < 0) putchar('-'), num = -num;
	stack<char> SSS;
	do SSS.push(num % 10 + '0');
	while (num /= 10);
	while (!SSS.empty())
		putchar(SSS.top()), SSS.pop();
	putchar('
');
	return;
}

typedef long long ll;

const int _N = 120000;
const int INF = 1e9;

priority_queue<int> Q;
vector<int> G[_N];
int cnt[_N];

int main()
{
	int N, M;
	rd(N), rd(M);
	for (int a, b, i = 1; i <= M; ++i) {
		rd(a), rd(b);
		G[a].push_back(b);
		++cnt[b];
	}
	for (int i = 1; i <= N; ++i)
		if (!cnt[i]) Q.push(i);
	int mn = INF;
	ll ans = 0;
	while (!Q.empty()) {
		int t = Q.top();
		Q.pop();
		mn = min(mn, t);
		ans += mn;
		for (int i = G[t].size() - 1; i >= 0; --i)
			if (!--cnt[G[t][i]]) Q.push(G[t][i]);
	}
	pt(ans);
	return 0;
}

3.) wjj 的零一序列

这道题类似 wxh 学长讲过的一道 Codeforces 的题 Queries 。CF 的那道题更加复杂，需要把每个数按二进制拆位，然后用位数那么多棵线段树维护区间信息。这个拆位思想其他题也遇到过，非常有用！另外 wxh 大佬真强啊……当时讲了十多道题，现在已经在其他地方遇到过两道几乎一致的题啦。可能因为 CF 的题，大家都觉得改改就能重新再出一道题吧……
这题先对原序列求前缀异或序列，对后者维护一下区间 0 和 1 的数量，记为 $ v_0, v_1 $ ，然后询问 0 的答案是 $ v_0 cdot (v_0 - 1) / 2 + v_1 cdot (v_1 - 1) / 2 $ ，询问 1 的答案是 $ v_0 cdot v_1 $ 。注意询问原序列 $ [x, y] $ 区间时对应询问的前缀异或序列区间是 $ [x - 1, y] $ 。最后改悔一下，线段树动态开点要注意随时新建儿子节点，考试的时候用到还没建立的儿子节点的信息，更新了当前节点，然后就爆 0 了 OrzOrz 。

#include <cstdio>
#include <algorithm>
#include <stack>
#include <ctype.h>

using namespace std;

#define SC(a, b) (static_cast<a>(b))

template<typename T>
void rd(T &num)
{
	char tt;
	bool flag = 0;
	while (!isdigit(tt = getchar()) && tt != '-');
	if (tt == '-') num = 0, flag = 1;
	else num = tt - '0';
	while (isdigit(tt = getchar()))
		num = num * 10 + tt - '0';
	if (flag) num = -num;
	return;
}

template<typename T>
void pt(T num)
{
	if (num < 0) putchar('-'), num = -num;
	stack<char> SSS;
	do SSS.push(num % 10 + '0');
	while (num /= 10);
	while (!SSS.empty())
		putchar(SSS.top()), SSS.pop();
	putchar('
');
	return;
}

typedef long long ll;

const int _N = 5000000;

struct data {
	int v0, v1;
	data(int v0 = 0, int v1 = 0):
		v0(v0), v1(v1) { }
};

int Lazy[_N], L[_N], R[_N], V0[_N], V1[_N];
int Rt, Cnt, N, TTT;

void putdown(int &p, int l, int r)
{
	int mid = (l + r) >> 1;
	
	swap(V0[L[p]], V1[L[p]]), swap(V0[R[p]], V1[R[p]]);
	Lazy[p] ^= 1, Lazy[L[p]] ^= 1, Lazy[R[p]] ^= 1;
	return;
}

void modify(int &p, int l, int r, int s, int t)
{
	if (!p) p = ++Cnt, V0[p] = r - l + 1;
	if (s <= l && r <= t) {
		swap(V0[p], V1[p]);
		Lazy[p] ^= 1;
		return;
	}
	int mid = (l + r) >> 1;
	if (!L[p]) L[p] = ++Cnt, V0[L[p]] = mid - l + 1;
	if (!R[p]) R[p] = ++Cnt, V0[R[p]] = r - mid;
	if (Lazy[p])
		putdown(p, l, r);
	if (t >= l && s <= mid)
		modify(L[p], l, mid, s, t);
	if (t > mid && s <= r)
		modify(R[p], mid + 1, r, s, t);
	V0[p] = V0[L[p]] + V0[R[p]];
	V1[p] = V1[L[p]] + V1[R[p]];
	return;
}

data query(int &p, int l, int r, int s, int t)
{
	if (!p) p = ++Cnt, V0[p] = r - l + 1;
	if (s <= l && r <= t) {
		return data(V0[p], V1[p]);
	}
	int mid = (l + r) >> 1, s0 = 0, s1 = 0;
	if (!L[p]) L[p] = ++Cnt, V0[L[p]] = mid - l + 1;
	if (!R[p]) R[p] = ++Cnt, V0[R[p]] = r - mid;
	if (Lazy[p])
		putdown(p, l, r);
	if (t >= l && s <= mid) {
		data tmp = query(L[p], l, mid, s, t);
		s0 += tmp.v0, s1 += tmp.v1;
	}
	if (t > mid && s <= r) {
		data tmp = query(R[p], mid + 1, r, s, t);
		s0 += tmp.v0, s1 += tmp.v1;
	}
	return data(s0, s1);
}

int main()
{
	rd(N);
	for (int t, i = 1; i <= N; ++i) {
		rd(t);
		if (t) modify(Rt, 0, N, i, N);
	}
	rd(TTT);
	while (TTT--) {
		int ins, x, y;
		rd(ins), rd(x);
		if (ins == 2) {
			modify(Rt, 0, N, x, N);
		} else {
			rd(y);
			data t = query(Rt, 0, N, x - 1, y);
			if (ins == 0) {
				ll s = 0;
				if (t.v0 >= 2) s += SC(ll, t.v0) * (t.v0 - 1) / 2;
				if (t.v1 >= 2) s += SC(ll, t.v1) * (t.v1 - 1) / 2;
				pt(s);
			} else {
				pt(SC(ll, t.v0) * t.v1);
			}
		}
	}
	return 0;
}