Submission

PPPPPPPPPPP

Score: 100

User: Dormon

Problemset: เปิดไฟ

Language: cpp

Time: 0.112 second

Submitted On: 2025-01-03 20:33:07

#include <iostream>
#include <cstdint>
#include <cstring>
#include <vector>
#include <algorithm>
#include <functional>
#include <queue>
#include <numeric>
#include <array>
#include <iomanip> // cout << fixed << setprecision(n);

#define debug(...) Debug(#__VA_ARGS__, __VA_ARGS__)
using namespace std;
const bool TEST_CASE = 0;

template<typename T>
typename std::enable_if<std::is_integral<T>::value>::type
Debug(const char* name, T value) {
    std::cout << name << " : " << value << '\n';
}

template<typename T, typename... Args>
typename std::enable_if<std::is_integral<T>::value>::type
Debug(const char* names, T value, Args... args) {
    const char* comma = strchr(names, ',');
    std::cout.write(names, comma - names) << " : " << value << " | ";
    Debug(comma + 1, args...);
}
template<typename T> ostream& operator<<(ostream& out, vector<T>& a) {
    for(auto &x : a) out << x << ' '; 
    return out;
};

class LazySegmentTree {
    vector<int> tree, lazy;
    int n;

    void build(int u, int l, int r) {
        if (l == r){
            tree[u] = 0;
            return;
        }
        int mid = (l + r) / 2;
        build(2*u, l, mid);
        build(2*u+1, mid+1, r);
        tree[u] = tree[2*u] + tree[2*u+1];
    }

    void pushlz(int u, int l, int r) {
        if (lazy[u] % 2 != 0) {
            tree[u] = (r - l + 1) - tree[u];
            if (l != r) {
                lazy[2 * u] += lazy[u];
                lazy[2 * u + 1] += lazy[u];
            }
        }
        lazy[u] = 0;
    }

    void updateRange(int u, int start, int end, int l, int r) {
        pushlz(u, start, end);
        if (start > r || end < l)
            return;
        if (start >= l && end <= r){
            lazy[u] += 1;
            pushlz(u, start, end);
            return;
        }

        int mid = (start + end) / 2;
        updateRange(2 * u, start, mid, l, r);
        updateRange(2 * u + 1, mid + 1, end, l, r);
        tree[u] = tree[2 * u] + tree[2 * u + 1];
    }

    int queryRange(int u, int start, int end, int l, int r) {
        pushlz(u, start, end);
        if (start > r || end < l)
            return 0;
        if (start >= l && end <= r)
            return tree[u];
        int mid = (start + end) / 2;
        return queryRange(2 * u, start, mid, l, r) +
               queryRange(2 * u + 1, mid + 1, end, l, r);
    }

public:
    LazySegmentTree(int size) {
        n = size;
        tree.resize(4 * n, 0);
        lazy.resize(4 * n, 0);
        build(1, 1, n);
    }

    void update(int l, int r) {
        updateRange(1, 1, n, l, r);
    }

    int query(int l, int r) {
        return queryRange(1, 1, n, l, r);
    }
};

void solve(){
    int n, q;
    cin >> n >> q;
    LazySegmentTree tree(n);
    while (q--){
        int type, l, r;
        cin >> type >> l >> r;
        if (type)
            cout << tree.query(l, r) << '\n';
        else
            tree.update(l, r);
    }
}

#define DORMON

int main()
{
    #ifndef DORMON
        ios_base::sync_with_stdio(false); 
    #endif
    cin.tie(0);
    int q = 1; 
    if (TEST_CASE) cin >> q;
    while (q--){
        solve();
    }
}