线段树求助
查看原帖
线段树求助
1056103
Aalla楼主2023/8/3 15:39

调了好久了没搞出来

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll maxn=1000005;
ll tag[maxn<<2], w[maxn], a[maxn];
ll n, m, opt, x, y, k;
inline void push_up(int u) {
	w[u]=w[u*2]+w[u*2+1];
}
inline void build(int u, int L, int R) {
	if(L==R) {
		w[u]=a[L];
		return;
	}
	int M=(L+R)>>1;
	build(u*2, L, M);
	build(u*2+1, M+1, R);
	push_up(u);
}
inline bool InRange(int L, int R, int l, int r) {
	return (l<=L)&&(R<=r);
}
inline bool OutofRange(int L, int R, int l, int r) {
	return (L>r)||(R<l);
}
inline void make_tag(int u, int L, int R) {
	tag[u]^=1, w[u]=R-L+1-w[u];
}
inline void push_down(int u, int L, int R) {
	int M=(L+R)>>1;
	make_tag(u*2, M-L+1, tag[u]);
	make_tag(u*2+1, R-M, tag[u]);
	tag[u]=0;
}
inline ll query(int u, int L, int R, int l, int r) {
	if(InRange(L, R, l, r)) return w[u];
	else if(!OutofRange(L, R, l, r)) {
		int M=(L+R)>>1;
		push_down(u, L, R);
		return query(u*2, L, M, l, r)+query(u*2+1, M+1, R, l, r);
	} else return 0;
}
inline void update(int u, int L, int R, int l, int r, int x) {
	if(l<=L&&R<=r) make_tag(u, R, L);
	else if(!OutofRange(L, R, l, r)) {
		int M=(L+R)>>1;
		push_down(u, L, R);
		update(u*2, L, M, l, r, x);
		update(u*2+1, M+1, R, l, r, x);
		push_up(u);
	}
}
int main() {
	scanf("%lld %lld", &n, &m);
	while(m--) {
		scanf("%lld %lld %lld", &opt, &x, &y);
		if(opt==0) update(1, 1, n, x, y, k);
		else cout<<query(1, 1, n, x, y)<<endl;
	}
	return 0;
}
2023/8/3 15:39
加载中...