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)が与えられる場合を考える.

上図の□は反転回数を表している.つまり1,5は1回反転なので白,2,3,4,は2回反転なので黒.
このように加算していく.これを早く処理する.
まず(1,4)が与えられた時にはじめの1を+1し終わりの次の数の5を-1する.
次に(2,5)が与えられた時にはじめの2を+1し終わりの次の数の6を-1する.
最後に累積和を取る.
すると上の処理と同じ結果になる.

これを使って実装したコードは下のようになった.

#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;
}