結果

問題 No.2879 Range Flip Queries
ユーザー anago-pie
提出日時 2024-09-19 23:23:07
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 778 ms / 2,000 ms
コード長 3,126 bytes
コンパイル時間 2,152 ms
コンパイル使用メモリ 204,824 KB
最終ジャッジ日時 2025-02-24 09:35:03
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<n; i++)
#define debug 0
#define YES cout << "Yes" << endl;
#define NO cout << "No" << endl;
using ll = long long;
using ld = long double;
const int mod = 998244353;
const int MOD = 1000000007;
const double pi = atan2(0, -1);
const int inf = 1 << 31-1;
const ll INF = 1LL << 63 - 1;
#include <time.h>
#include <chrono>
//vectorの中身を空白区切りで出力
template<typename T>
void printv(vector<T> v) {
    for (int i = 0; i < v.size(); i++) {
        cout << v[i];
        if (i < v.size() - 1) {
            cout << " ";
        }
    }
    cout << endl;
}
//vectorの中身を改行区切りで出力
template<typename T>
void print1(vector<T> v) {
    for (auto x : v) {
        cout << x << endl;
    }
}
//二次元配列を出力
template<typename T>
void printvv(vector<vector<T>> vv) {
    for (vector<T> v : vv) {
        printv(v);
    }
}
//vectorを降順にソート
template<typename T>
void rsort(vector<T>& v) {
    sort(v.begin(), v.end());
    reverse(v.begin(), v.end());
}
//昇順priority_queueを召喚
template<typename T>
struct rpriority_queue {
    priority_queue<T, vector<T>, greater<T>> pq;
    void push(T x) {
        pq.push(x);
    }
    void pop() {
        pq.pop();
    }
    T top() {
        return pq.top();
    }
    size_t size() {
        return pq.size();
    }
    bool empty() {
        return pq.empty();
    }
};
//mod mod下で逆元を算出する
//高速a^n計算(mod ver.)
ll power(ll a, ll n) {
    if (n == 0) {
        return 1;
    }
    else if (n % 2 == 0) {
        ll x = power(a, n / 2);
        x *= x;
        x %= mod;
        return x;
    }
    else {
        ll x = power(a, n - 1);
        x *= a;
        x %= mod;
        return x;
    }
}
//フェルマーの小定理を利用
ll modinv(ll p) {
    return power(p, mod - 2) % mod;
}
//Mexを求める
struct Mex {
    map<int, int> mp;
    set<int> s;
    Mex(int Max) {
        for (int i = 0; i <= Max; i++) {
            s.insert(i);
        }
    }
    int _mex = 0;
    void Input(int x) {
        mp[x]++;
        s.erase(x);
        if (_mex == x) {
            _mex = *begin(s);
        }
    }
    void Remove(int x) {
        if (mp[x] == 0) {
            cout << "Mex ERROR!: NO VALUE WILL BE REMOVED" << endl;
        }
        mp[x]--;
        if (mp[x] == 0) {
            s.insert(x);
            if (*begin(s) == x) {
                _mex = x;
            }
        }
    }
    int mex(){
        return _mex;
    }
};
struct SegTree {
    int n = 1;
    vector<int> tree;
    SegTree(int N) {
        while (n < N) {
            n *= 2;
        }
        vector<int> v(n*2, 0);
        swap(tree, v);
    }
    void Add(int l, int r, int u, int t, int now) {
        if (r <= u || l >= t) {
            return;
        }
        else if (l <= u && r >= t) {
            tree[now]++;
        }
        else {
            Add(l, r, u, (u + t) / 2, now * 2 + 1);
            Add(l, r, (u + t) / 2, t, now * 2 + 2);
        }
    }
    int Calc(int now) {
        if (now == 0) {
            return tree[0];
        }
        else {
            int p = Calc((now - 1) / 2);
            return p + tree[now];
        }
    }
    void Query(int l, int r) {
        Add(l, r + 1, 0, n, 0);
    }
    int Ans(int i) {
        return Calc(n - 1 + i);
    }
    void Set(int i, int k) {
        tree[n - 1 + i] = k;
    }
};
int main() {
    int N, Q;
    cin >> N >> Q;
    SegTree st(N);
    rep(i, N) {
        int a;
        cin >> a;
        st.Set(i, a);
    }
    rep(q, Q) {
        int l, r;
        cin >> l >> r;
        l--; r--;
        st.Query(l, r);
    }
    rep(i, N) {
        cout << st.Ans(i) % 2 << " ";
    }
    cout << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0