http://codeforces.com/contest/1401

E. Divide Square

 

题意：在由 (0,0),(0,106),(106,0),(106,106)(0,0),(0,10^6),(10^6,0),(10^6,10^6) 围成的正方形里，给定几条竖直或水平的线段，每条线段至少有一端接触正方形的一边，问这些线段把正方形分成几块。

树状数组+扫描线

当初刚刚接触扫描线也是因为一道正方形切割的问题。本题也是类似。

关键点在于，一条线段如果与正方形两边都相连，则每一条这样的线段都可以增加一块。并且，由于每条线段至少有一端在边框上，所以每一次线段相交都能够新增一块。

输入时顺便处理分割整个正方形的情况。接下来就是要算交点个数，老套路了，把每条竖线拆成两个点，横线按照 y 坐标排序，遍历横线，扫描线维护所有穿过当前 y 坐标的竖线的个数，树状数组维护横线所在 x 区间内的竖线个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2e6 + 10;
const ll mod = 1e9 + 7;
int n, m, M = 1000000;
ll ans = 1ll;
struct X
{
	int lx, rx, y;
	bool operator<(const X& b)const {
		return y < b.y;
	}
}a[N];	//横
struct Q
{
	int y, tp, x;
	bool operator<(const Q& b)const {
		return y == b.y ? tp < b.tp : y < b.y;
	}
};
int ad[]{ 1,-1 };
vector<Q>vc;
int sum[N];
int lowbit(int x) { return x & -x; }
void add(int p, int x) {
	for (int i = p; i <= M; i += lowbit(i)) {
		sum[i] += x;
	}
}
int qry(int r) {
	int res = 0;
	for (int i = r; i > 0; i -= lowbit(i)) {
		res += sum[i];
	}
	return res;
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%d%d%d", &a[i].y, &a[i].lx, &a[i].rx);
		if (a[i].lx == 0 && a[i].rx == M)ans++;
	}
	sort(a + 1, a + n + 1);
	for (int i = 1; i <= m; i++) {
		int ly, ry, x;
		scanf("%d%d%d", &x, &ly, &ry);
		if (ly == 0 && ry == M)ans++;
		vc.push_back(Q{ ly,0,x });
		vc.push_back(Q{ ry,1,x });
	}
	sort(vc.begin(), vc.end());
	m = (int)vc.size();
	int nw = 0;
	for (int i = 1; i <= n; i++) {
		while (nw < m && (vc[nw].y < a[i].y || vc[nw].y == a[i].y&&vc[nw].tp == 0)) {
			add(vc[nw].x, ad[vc[nw].tp]);
			nw++;
		}
		ans += qry(a[i].rx) - qry(a[i].lx - 1);
	}
	printf("%lld\n", ans);
	return 0;
}

 

F. Reverse and Swap

 

题意：给定一个 2n2^n 个元素的数组，四种操作：1. 把第 x 个元素改为 k；2. 把数组按照 2k2^k 个元素分一块，并各自翻转每一块；3. 把数组按照 2k+12^{k+1} 个元素分一块，并在每一块内交换左半部分后右半部分；4. 查询 [l,r][l,r] 的元素和。

线段树

读完题目应该就很自然想到线段树了。并且要从各种翻转联想到区间更改时的懒标记。

翻转可以视为不断交换左右区间，同时不断扩大区间大小。

所以可以给区间设置一个 rev 标记，表明是否交换了左右儿子。

本题关键就在于所有的操作都是对于所有长度为某个值的区间进行的，所以可以不用给每个区间都标记，而是标记线段树上某一个深度是否交换了左右儿子。同一深度要么都交换了，要么都没有交换。

还有一个关键点在于线段树上交换儿子，并不会改变儿子的父亲，也就是说节点 u 的两个儿子无论怎么操作，仍然是 u 的儿子，只不过可能左儿子变右儿子，右儿子变左儿子。那么就可以放心地维护区间的和，并和原来一样查询了。

所以，翻转操作就是从线段树倒数第二层（记为 1 ）开始向上到第 k 层，把每一层打上 rev 标记。

交换操作就是只对第 k+1 层打上标记。

单点修改与查询类似，先找到要修改的位置，途中根据儿子是否交换过来判断进入左儿子还是右儿子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 5e5 + 10;
const ll mod = 1e9 + 7;
int n, q;
ll a[N];
#define mid ((l+r)>>1)
#define lson dep-1,l,mid,rt<<1^rev[dep]
#define rson dep-1,mid+1,r,rt<<1|1^rev[dep]
ll tr[N << 2];
int rev[20];
void up(int rt) {
	tr[rt] = tr[rt << 1] + tr[rt << 1 | 1];
}
void build(int dep, int l, int r, int rt) {
	if (l == r) {
		tr[rt] = a[l];
		return;
	}
	build(lson);
	build(rson);
	up(rt);
}
ll qry(int ql, int qr, int dep, int l, int r, int rt) {
	if (ql <= l && qr >= r)return tr[rt];
	ll res = 0ll;
	if (ql <= mid)res += qry(ql, qr, lson);
	if (qr > mid)res += qry(ql, qr, rson);
	return res;
}
void cg(int q, int x, int dep, int l, int r, int rt) {
	if (l == r) {
		tr[rt] = x;
		return;
	}
	if (q <= mid)cg(q, x, lson);
	else cg(q, x, rson);
	up(rt);
}
int main() {
	scanf("%d%d", &n, &q);
	for (int i = 1; i <= (1 << n); i++)scanf("%lld", &a[i]);
	build(n, 1, (1 << n), 1);
	while (q--) {
		int op;
		scanf("%d", &op);
		if (op == 1) {
			int x, k;
			scanf("%d%d", &x, &k);
			cg(x, k, n, 1, (1 << n), 1);
		}
		else if (op == 2) {
			int k;
			scanf("%d", &k);
			if (!k)continue;
			for (int i = 1; i <= k; i++)rev[i] ^= 1;
		}
		else if (op == 3) {
			int k;
			scanf("%d", &k);
			rev[k + 1] ^= 1;
		}
		else {
			int l, r;
			scanf("%d%d", &l, &r);
			printf("%lld\n", qry(l, r, n, 1, (1 << n), 1));
		}
	}
	return 0;
}