论用集合维护的可行性
查看原帖
论用集合维护的可行性
799877
AK_heaven楼主2023/11/29 20:56

请教各位,这道题我想要用集合来做,但是全wa,信息显示的是输出了0,求教:

代码如下:

#include <bits/stdc++.h>
#define ls (p<<1)
#define rs (p<<1|1)
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
ll n, m, q;

struct Seg {
	ll l, r;
	ll tag;
	set<int> sum;
}tr[maxn<<2];

void pushup(int p) {
	tr[p].sum.clear();
	for(auto it = tr[ls].sum.begin(); it != tr[ls].sum.end(); it++) {
		tr[p].sum.insert(*it);
	}
	for(auto it = tr[rs].sum.begin(); it != tr[rs].sum.end(); it++) {
		tr[p].sum.insert(*it);
	}
}

void pushdown(int p) {
	if(tr[p].tag) {
		tr[ls].sum.clear();
		tr[rs].sum.clear();
		  tr[ls].sum.insert(tr[p].tag);
		  tr[rs].sum.insert(tr[p].tag);
		tr[ls].tag = tr[rs].tag = tr[p].tag;
		tr[p].tag = 0;
	}
}

void build(int p, int l, int r) {
	tr[p].l = l, tr[p].r = r;
	tr[p].sum.insert(1);
	if(l == r) return ;
	int mid = (l+r)/2;
	build(ls, l, mid);
	build(rs, mid+1, r);
}

void update(int p, int x, int y, int k) {
	if(x <= tr[p].l && tr[p].r <= y) {
		tr[p].sum.clear();
		tr[p].sum.insert(k);
		tr[p].tag = k;
		return ;
	}
	pushdown(p);
	int mid = (tr[p].l + tr[p].r)/2;
	if(x <= mid) update(ls, x, y, k);
	if(y > mid) update(rs, x, y, k);
	pushup(p);
}
set <int> ans;
void query(int p, int x, int y) {
	if(x <= tr[p].l && tr[p].r <= y) {	
		for(auto it = tr[p].sum.begin(); it != tr[p].sum.end(); it++)
			ans.insert(*it);
		return ;
	}
	int mid = (tr[p].l + tr[p].r)/2;
	if(x <= mid) query(ls, x, y);
	if(y > mid) query(rs, x, y);
}

int main() {
	cin >> n >> m >> q;
	build(1, 1, n);
	char op; int x, y, k;
	while(q--) {
		cin >> op >> x >> y;
		if(op == 'C') {
			cin >> k;
			update(1, x, y, k);
		}
		else {
			ans.clear();
			query(1, x, y);
//			for(auto it = ans.begin(); it != ans.end(); it++)
//			  cout << *it << " ";
//			cout << '\n';
			cout << ans.size() << '\n';
		}
	}
	return 0;
}
2023/11/29 20:56
加载中...