线段树求调!
查看原帖
线段树求调!
519573
Daniel_yao楼主2022/9/19 13:25
#include <bits/stdc++.h>
#define ll long long
#define rint register int
#define For(i,l,r) for(int i=l;i<=r;i++)
#define FOR(i,r,l) for(int i=r;i>=l;i--)
#define mod 1000000007

using namespace std;

inline int read() {
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}

const int N = 500010;

struct Node {
	int l, r;
	int num;
}t[N << 2]; 

int n = read(), m = read(), add[N]; 

void pushup(int p) {
	t[p].num = t[p<<1].num + t[p<<1|1].num;
}

int len(int p) {
	return t[p].r - t[p].l + 1;
}

void brush(int p) {
	add[p] ^= 1;
	t[p].num = len(p) - t[p].num;
}

void pushdown(int p) {
	if(add[p]) {
		brush(p<<1); brush(p<<1|1);
		add[p] = 0;
	}
}

void build(int p, int l, int r) {
	t[p].l = l, t[p].r = r;
	if(l == r) {
		t[p].num = 0;
		return ;
	}
	int mid = l + r >> 1;
  build(p<<1, l, mid);
  build(p<<1|1, mid + 1, r);
  pushup(p);
}

void update(int p, int l, int r) {
	if(l <= t[p].l && t[p].r <= r) {
		brush(p);
		return ;
	}
	int mid = t[p].l + t[p].r >> 1;
	pushdown(p);
	if(l <= mid) {
		update(p<<1, l, r);
	}
	if(r > mid) {
		update(p<<1|1, l, r); 
	}
	pushup(p);
}

int query(int p, int l, int r) {
	if(l <= t[p].l && t[p].r <= r) {
		return t[p].num;
	}
	int mid = t[p].l + t[p].r >> 1;
	int ans = 0;
	pushdown(p);
	if(l <= mid) {
		ans += query(p<<1, l, r);
	}
	if(r > mid) {
		ans += query(p<<1|1, l, r);
	}
	return ans;
}

signed main() {
	build(1, 1, n);
	while(m--) {
		int op = read();
		if(op == 1) {
			int l = read(), r = read();
			update(1, l, r);
		} else {
			int i = read();
			if(i == 1) cout << query(1, 1, 1);
			else cout << query(1, 1, i) - query(1, 1, i-1) << '\n';
		}
	}
  return 0;
}
2022/9/19 13:25
加载中...