[POI2014]KAR-Cards

题目链接：

题目分析：

线段树妙题，感觉思路奇奇怪怪的，虽然对我来说不是“线段树菜题”（\(ldx\)神仙\(blog\)原话）\(QAQ\)

考虑怎么样维护可合并的信息解决这道题

首先有一个很明显的贪心，一张卡片正反面肯定是能小就小，不带修的话直接就过了

带修的话怎么处理呢，考虑在线段树上维护一个\(sum[0/1]\)，表示这个节点\(l\)位置上卡片选正/反面的时候\(r\)位置上卡片的最小取值，不合法赋\(INF\)

重点在\(pushup\)里面，每次\(pushup\)的时候把左子区间维护的两个\(sum\)分别和右子区间左端点的两个值比较一下看合不合法，不合法赋\(INF\)（感觉说的不是很清楚，自己脑补一下\(or\)看代码可能会好懂一点

每次交换可以看做单点修改

代码：

#include<bits/stdc++.h>

#define N (300000 + 10)

using namespace std;

inline int read() {

	int cnt = 0, f = 1; char c = getchar();

	while (!isdigit(c)) {if (c == '-') f = -f; c = getchar();}

	while (isdigit(c)) {cnt = (cnt << 3) + (cnt << 1) + c - '0'; c = getchar();}

	return cnt * f;

}

const int INF = 1000000000 + 7;

int n, m;

int x, y;

int a[N], b[N];

struct node {

	int l, r, sum[2];

	#define l(p) tree[p].l

	#define r(p) tree[p].r

	#define sum0(p) tree[p].sum[0]

	#define sum1(p) tree[p].sum[1]

}tree[N << 2];

void pushup(int p) {

	sum0(p) = sum1(p) = INF;

	if (sum0(p << 1) <= a[l(p << 1 | 1)]) sum0(p) = sum0(p << 1 | 1);

	if (sum0(p << 1) <= b[l(p << 1 | 1)]) sum0(p) = min(sum0(p), sum1(p << 1 | 1));

	if (sum1(p << 1) <= a[l(p << 1 | 1)]) sum1(p) = sum0(p << 1 | 1);

	if (sum1(p << 1) <= b[l(p << 1 | 1)]) sum1(p) = min(sum1(p), sum1(p << 1 | 1));

}

void build(int p, int l, int r) {

	l(p) = l, r(p) = r;

	if (l == r) {sum0(p) = a[l], sum1(p) = b[l]; return;}

	int mid = (l + r) >> 1;

	build (p << 1, l, mid);

	build (p << 1 | 1, mid + 1, r);

	pushup(p);

}

void modify(int p, int x, int u, int v) {

	if (u > v) swap(u, v);

	if (l(p) == r(p)) {sum0(p) = a[l(p)] = u, sum1(p) = b[l(p)] = v; return;}

	int mid = (l(p) + r(p)) >> 1;

	if (x <= mid) modify(p << 1, x, u, v);

	else modify(p << 1 | 1, x, u, v);

	pushup(p);

}

int cura, curb;

int main() {

	n = read();

	for (register int i = 1; i <= n; i++) {

		a[i] = read(), b[i] = read();

		if (a[i] > b[i]) swap(a[i], b[i]);

	}

	build(1, 1, n);

	m = read();

	for (register int i = 1; i <= m; i++) {

		x = read(), y = read();

		cura = a[x], curb = b[x];

		modify(1, x, a[y], b[y]), modify(1, y, cura, curb);

		if (sum0(1) == INF && sum1(1) == INF) printf("NIE\n");

		else printf("TAK\n");

	}

	return 0;

}

巴特西

[POI2014]KAR-Cards

题目链接：

题目分析：

代码：

最新文章

热门文章