专栏文章

题解：UVA11402 Ahoy, Pirates!

BBobi2014
UVA11402题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minpbq0u
此快照首次捕获于
2025/12/02 06:09
3 个月前
此快照最后确认于
2025/12/02 06:09
3 个月前
查看原文
这是一道可癌的线段树题。

前置知识

思路

考虑使用 33 个懒标记，分别记录是否全 11、是否全 00、是否需要翻转。
pushdown 时先考虑 00 和 11 再考虑是否翻转，修改时如果改成 00 或 11，那么清除其他的 tag，把对应的 tag 改成 true。
接下来就是普通的线段树了，一组测试数据的时间复杂度为 O(Qlog⁡n)O(Q \log n)。

Code

CPP
#include<bits/stdc++.h>
using namespace std;
const int N = 1024010;
int Q,n,m,T;
string s,str;
namespace SegmentTree{
	struct node{
		int l,r,sum;
		bool tag_0,tag_1,tag_inv;
	} tri[N << 2];
	void build(int p,int l,int r){
		tri[p].l = l,tri[p].r = r;
		tri[p].tag_0 = tri[p].tag_1 = tri[p].tag_inv = false;
		if(l == r){
			tri[p].sum = str[l] - '0';
			return;
		}
		int mid = (l + r) >> 1;
		build(p << 1,l,mid);
		build(p << 1 | 1,mid + 1,r);
		tri[p].sum = tri[p << 1].sum + tri[p << 1 | 1].sum;
	}
	void pushdown(int p){
		if(tri[p].tag_0 == true){
			tri[p << 1].tag_0 = tri[p << 1 | 1].tag_0 = true;
			tri[p << 1].tag_1 = tri[p << 1 | 1].tag_1 = false;
			tri[p << 1].tag_inv = tri[p << 1 | 1].tag_inv = false;
			tri[p << 1].sum = 0;
			tri[p << 1 | 1].sum = 0;
			tri[p].tag_0 = false;
		}
		if(tri[p].tag_1 == true){
			tri[p << 1].tag_0 = tri[p << 1 | 1].tag_0 = false;
			tri[p << 1].tag_1 = tri[p << 1 | 1].tag_1 = true;
			tri[p << 1].tag_inv = tri[p << 1 | 1].tag_inv = false;
			tri[p << 1].sum = tri[p << 1].r - tri[p << 1].l + 1;
			tri[p << 1 | 1].sum = tri[p << 1 | 1].r - tri[p << 1 | 1].l + 1;
			tri[p].tag_1 = false;
		}
		if(tri[p].tag_inv == true){
			tri[p << 1].tag_inv ^= true;
			tri[p << 1 | 1].tag_inv ^= true;
			tri[p << 1].sum = (tri[p << 1].r - tri[p << 1].l + 1) - tri[p << 1].sum;
			tri[p << 1 | 1].sum = (tri[p << 1 | 1].r - tri[p << 1 | 1].l + 1) - tri[p << 1 | 1].sum;
			tri[p].tag_inv = false;
		}
	}
	void update_0(int p,int l,int r){
		if(tri[p].l >= l and tri[p].r <= r){
			tri[p].tag_0 = true;
			tri[p].tag_1 = false;
			tri[p].tag_inv = false;
			tri[p].sum = 0;
			return;
		}
		pushdown(p);
		int mid = (tri[p].l + tri[p].r) >> 1;
		if(l <= mid){
			update_0(p << 1,l,r);
		}
		if(r > mid){
			update_0(p << 1 | 1,l,r);
		}
		tri[p].sum = tri[p << 1].sum + tri[p << 1 | 1].sum;
	}
	void update_1(int p,int l,int r){
		if(tri[p].l >= l and tri[p].r <= r){
			tri[p].tag_0 = false;
			tri[p].tag_1 = true;
			tri[p].tag_inv = false;
			tri[p].sum = tri[p].r - tri[p].l + 1;
			return;
		}
		pushdown(p);
		int mid = (tri[p].l + tri[p].r) >> 1;
		if(l <= mid){
			update_1(p << 1,l,r);
		}
		if(r > mid){
			update_1(p << 1 | 1,l,r);
		}
		tri[p].sum = tri[p << 1].sum + tri[p << 1 | 1].sum;
	}
	void invert(int p,int l,int r){
		if(tri[p].l >= l and tri[p].r <= r){
			tri[p].tag_inv ^= true;
			tri[p].sum = (tri[p].r - tri[p].l + 1) - tri[p].sum;
			return;
		}
		pushdown(p);
		int mid = (tri[p].l + tri[p].r) >> 1;
		if(l <= mid){
			invert(p << 1,l,r);
		}
		if(r > mid){
			invert(p << 1 | 1,l,r);
		}
		tri[p].sum = tri[p << 1].sum + tri[p << 1 | 1].sum;
	}
	int query(int p,int l,int r){
		if(tri[p].l >= l and tri[p].r <= r){
			return tri[p].sum;
		}
		pushdown(p);
		int mid = (tri[p].l + tri[p].r) >> 1,ans = 0;
		if(l <= mid){
			ans += query(p << 1,l,r);
		}
		if(r > mid){
			ans += query(p << 1 | 1,l,r);
		}
		return ans;
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> Q;
	for(int i = 1;i <= Q;i ++){
		cout << "Case " << i << ":\n";
		str = " ";
		cin >> n;
		while(n --){
			cin >> m >> s;
			while(m --){
				str += s;
			}
		}
		n = str.size() - 1;
		SegmentTree::build(1,1,n);
		cin >> T;
		m = 0;
		while(T --){
			char op;
			int l,r;
			cin >> op >> l >> r;
			l ++,r ++;
			if(op == 'F'){
				SegmentTree::update_1(1,l,r);
			}else if(op == 'E'){
				SegmentTree::update_0(1,l,r);
			}else if(op == 'I'){
				SegmentTree::invert(1,l,r);
			}else{
				cout << "Q" << ++m << ": " << SegmentTree::query(1,l,r) << "\n";
			}
		}
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...