为啥窝写的线段树 TLE 了……
查看原帖
为啥窝写的线段树 TLE 了……
421781
liuzimingc楼主2021/9/12 10:23

RT。只 AC 两个点,其他全 T,代码如下:

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define ULL unsigned long long
#define LD long double
#define PII pair<int, int>
#define PDD pair<double, double>
#define PQ priority_queue
const int MAXN = 1e5 + 5;

template <typename T> void read(T &x) {x = 0; T f = 1; char tem = getchar (); while (tem < '0' || tem > '9') {if (tem == '-') f = -1; tem = getchar();} while (tem >= '0' && tem <= '9') {x = (x << 1) + (x << 3) + tem - '0'; tem = getchar();} x *= f;}
template <typename T> void write(T x) {if (x < 0) {x = -x; putchar ('-');} if (x > 9) write (x / 10); putchar (x % 10 + '0');}

int n, m, c, a, b;
struct tree {
    int l, r, v, add;
} t[MAXN << 2];

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

void pushdown(int p) {
    if (!t[p].add) return;
    t[p << 1].v = t[p << 1].r - t[p << 1].l + 1 - t[p << 1].v;
    t[p << 1 | 1].v = t[p << 1 | 1].r - t[p << 1 | 1].l + 1 - t[p << 1 | 1].v;
    t[p << 1].add ^= 1; t[p << 1 | 1].add ^= 1;
    t[p].add = 0;
}

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

void change(int p, int l, int r) {
    if (t[p].l == t[p].r) {
        t[p].v = t[p].r - t[p].l + 1 - t[p].v;
        // v 维护区间和
        // 那么在取反操作前区间内 1 的个数为 v,则取反后区间内 0 的个数为 v,即区间 1 的个数为 len - v = r - l + 1 - v
        t[p].add ^= 1;
        return;
    }
    pushdown(p);
    int mid = (t[p].l + t[p].r) >> 1;
    if (l <= mid) change(p << 1, l, r);
    if (r > mid) change(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].v;
    int mid = (t[p].l + t[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() {
#ifndef ONLINE_JUDGE
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
#endif
    read(n); read(m);
    bulid(1, 1, n);
    while (m--) {
        read(c); read(a); read(b);
        if (c) {write(query(1, a, b)); putchar('\n');}
        else change(1, a, b);
    }
    return 0;
}
2021/9/12 10:23
加载中...