洛谷P5057 [CQOI2006]简单题(线段树)
程序员文章站
2023-11-17 22:47:04
题意 "题目链接" Sol 紫色的线段树板子题??。。。 ......
题意
sol
紫色的线段树板子题??。。。
#include<iostream> #include<cstdio> #include<cmath> using namespace std; const int maxn = 1e6 + 10; inline int read() { char c = getchar(); int x = 0, f = 1; while (c < '0' || c > '9') {if (c == '-')f = -1; c = getchar();} while (c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();} return x * f; } int n, m; #define ls k << 1 #define rs k << 1 | 1 struct node { int l, r, w, f; }t[maxn]; void build(int k, int ll, int rr) { t[k].l = ll; t[k].r = rr; t[k].w = -1; t[k].f = 0; if(ll == rr) {t[k].w = 0; return ;} int mid = (t[k].l + t[k].r) >> 1; build(ls, ll, mid); build(rs, mid + 1, rr); } void reverse(int k, int ll, int rr) { if(ll <= t[k].l && t[k].r <= rr) {t[k].f ^= 1; return ;} int mid = (t[k].l + t[k].r) >> 1; if(ll <= mid) reverse(ls, ll, rr); if(rr > mid) reverse(rs, ll, rr); } int query(int k, int pos) { int ans = t[k].f; if(t[k].l == t[k].r) return ans; int mid = (t[k].l + t[k].r) >> 1; if(pos <= mid) ans ^= query(ls, pos); if(pos > mid) ans ^= query(rs, pos); return ans; } int main() { n = read(); m = read(); build(1, 1, n); while(m--) { int opt = read(); if(opt == 1) { int l = read(), r = read(); reverse(1, l, r); } else { printf("%d\n", query(1, read())); } } return 0; }