ABC 035 C - オセロ

問題

問題概要

オセロの向きを求める。

解法

一つずつやっていたらO(NQ)になるので、lとrの位置だけを記録してそれぞれの場所を何回ひっくり返されたかを記録すれば良い。ひっくり返された回数が、奇数であれば1、偶数であれば0である。区間に一様に1を加算できれば良いので、遅延セグメントtreeで区間に一様加算をやり、最後にそれぞれの位置の偶奇を調べた。
1次元imosでもできるみたい。考えてみると、場所への人の出入りの時刻がわかっているときの、最多人数の時刻を求める問題と同じになる。
imos法についての参考

satanic0258.hatenablog.com

ミス

オーバーキル

コード

遅延セグtree

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;

//(1)区間に一様加算 (2)区間の合計値
struct segtree{
public:
    const int SIZE = 1 << 18;
    //seg:区間の合計値 lazy:区間に対して、加える値でまだ遅延しているもの
    vector<ll> seg, lazy;//segは欲しい情報 lazyは区間に対する一様な処理を示すもの
    segtree():seg(SIZE * 2), lazy(SIZE * 2){}
    void lazy_evaluate(int k, int l, int r){//遅延情報の適用方法
        if(lazy[k] != 0){
            seg[k] += lazy[k];//区間[l,r)にすべて同じ値を追加することになっていて、segには合計値が入っているので、加える値を足す
            if(r  - l > 1){
                lazy[k * 2 + 1] += lazy[k];//遅延を左の子に伝搬
                lazy[k * 2 + 2] += lazy[k];//遅延を右の子に伝搬
            }
            lazy[k] = 0;//ノードkは伝搬完了
        }
    }
    void update(int a, int b, int k, int l, int r, int x){
        lazy_evaluate(k, l, r);
        if(r <= a || b <= l) return;
        if(a <= l && r <= b){
            lazy[k] += x; //加える
            lazy_evaluate(k, l, r);
        }else{
            update(a, b, k * 2 + 1, l, (l + r) / 2, x);
            update(a, b, k * 2 + 2, (l + r) / 2, r, x);
            seg[k] = seg[k * 2 + 1] + seg[k * 2 + 2]; //区間の合計
        }
    }  
    ll query(int a, int b, int k, int l, int r){
        lazy_evaluate(k, l, r);
        if(r <= a || b <= l) return 0;//合計に影響のないもの
        if(a <= l && r <= b) return seg[k];
        ll x = query(a, b, k * 2 + 1, l, (l + r) / 2);
        ll y = query(a, b, k * 2 + 2, (l + r) / 2, r);
        return x + y; //左右の合計を
    }
    //update(a,b,x) := [a,b)を全てxを加える
    void update(int a, int b, int x){update(a, b, 0, 0, SIZE, x);}
    //query(a,b) := [a,b)に対する合計値を求める
    ll query(int a, int b){return query(a, b, 0, 0, SIZE);}
};

int main(void){
    int n, q; cin >> n >> q;
    segtree st;
    rep(i, q){
        int l, r; cin >> l >> r;
        l--; r--;
        st.update(l, r + 1, 1);
    }
    string ans = "";
    rep(i, n){
        if(st.query(i, i + 1) % 2 == 0) ans += '0';
        else ans += '1';
    }
    cout << ans << endl;
    return 0;
}

1次元imos

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;

int n, q;

vector<int> imos_one(vector<int> baseimos){
    int basesize = baseimos.size();
    vector<int> imos(basesize, 0); 
    imos[0] = baseimos[0];
    for(int i = 1; i < basesize; ++i){
        imos[i] = imos[i - 1] + baseimos[i];
    }
    return imos;
}

int main(void){
    cin >> n >> q;
    vector<int> v(n + 1, 0);
    rep(i, q){
        int l, r; cin >> l >> r;
        l--, r--;
        v[l]++;
        v[r + 1]--;
    }
    auto ret = imos_one(v);
    string s  = "";
    rep(i, n){
        if(ret[i] % 2 == 0) s += '0';
        else s += '1';
    }
    cout << s << endl;
    return 0;
}