紙媒体で管理するとなくなりがちなのでブログで進捗などを管理することにしました
※殆どの記事は自分自身のためだけにかいています.他人に見せられるレベルには至っていません...

ABC035_C

一列に並んだオセロ(最初は全て黒)を指定された左と右の位置で反転を繰り返すという問題.
普通にやっていたら配列サイズ200,000、指定位置の個数や左,右の範囲が大きい場合でTLEを起こす.
普通にやった場合の解

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a[200010]={0};
    int n,q,l,r;
    cin>>n>>q;
    
    while(q--){
        cin>>l>>r;
        for(int i=l;i<=r;i++){
            a[i] = ~a[i];
        }
    }
    for(int i=1;i<=n;i++){
        cout<<(a[i]==0?0:1);
    }
    cout<<endl;
    return 0;
}

早くするには「いもす法」を使うらしい.
ここで例として(1,4),(2,5)が与えられる場合を考える.
f:id:umashika5555:20170312210120j:plain
上図の□は反転回数を表している.つまり1,5は1回反転なので白,2,3,4,は2回反転なので黒.
このように加算していく.これを早く処理する.
まず(1,4)が与えられた時にはじめの1を+1し終わりの次の数の5を-1する.
次に(2,5)が与えられた時にはじめの2を+1し終わりの次の数の6を-1する.
最後に累積和を取る.
すると上の処理と同じ結果になる.
f:id:umashika5555:20170312210320j:plain
これを使って実装したコードは下のようになった.

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,q,l,r,a[200010]={0};
    cin>>n>>q;
    while(q--){
        cin>>l>>r;
        a[l]++;
        a[r+1]--;
    }
    for(int i=1;i<n;i++){
        a[i+1]+=a[i];
    }
    for(int i=1;i<=n;i++){
        cout<<(a[i]%2?1:0);
    }
    cout<<endl;
    return 0;
}