ABC-035-C オセロ

■■■問題■■■

黒の面に'0'、白の面に'1'が書かれたN個のオセロの駒が、
どの駒も黒の面が上を向くように一列に並べられています。

その後、ある区間にある駒を全て裏返すという操作がQ回だけ行なわれました。
具体的にはi回目の操作においては、左からli番目の駒からri番目の駒までの駒全てが裏返されました。

最終的な盤面を求めてください。

■■■入力■■■

N Q
l1 r1
・
・
・
lQ rQ

●1行目に駒の数と操作回数を表す2つの整数N,Q(1 <= N,Q <= 20万)が空白区切りで与えられる。
●2行目から続くQ行のうちi行目においては、
  i回目の操作の範囲を表す2つの整数 li,ri(1 <= li <= ri <= N)が空白区切りで与えられる。

■■■出力■■■

最終的な盤面を表す文字列Sを1行に出力せよ。
Sの左からi文字目は左からi番目の駒の上向きの面に書かれた数字となる。改行を忘れないこと。

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "Input1";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("5 4");
            WillReturn.Add("1 4");
            WillReturn.Add("2 5");
            WillReturn.Add("3 3");
            WillReturn.Add("1 5");
            //01010
            //盤面ははじめ00000です。
            //1回目の操作により、盤面は11110となります。
            //2回目の操作により、盤面は10001となります。
            //3回目の操作により、盤面は10101となります。
            //4回目の操作により、盤面は01010となります。
            //最終的な盤面である01010が求める答えです。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("20 8");
            WillReturn.Add("1 8");
            WillReturn.Add("4 13");
            WillReturn.Add("8 8");
            WillReturn.Add("3 18");
            WillReturn.Add("5 20");
            WillReturn.Add("19 20");
            WillReturn.Add("2 7");
            WillReturn.Add("4 9");
            //10110000011110000000
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();

        int[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(X => int.Parse(X)).ToArray();

        //いもす法で解く
        SplitAct(InputList[0]);
        int N = wkArr[0];
        int[] BanArr = new int[N];
        int UB = BanArr.GetUpperBound(0);

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            int I = wkArr[0];
            int R = wkArr[1];

            int FromSumInd = I - 1;
            int ToSumInd = R;

            BanArr[FromSumInd]++;
            if (ToSumInd <= UB) BanArr[ToSumInd]--;
        }

        //累積和を求める
        int RunSum = 0;
        var sb = new System.Text.StringBuilder();
        for (int I = 0; I <= UB; I++) {
            RunSum += BanArr[I];
            sb.Append(RunSum % 2);
        }
        Console.WriteLine(sb.ToString());
    }
}

解説

いもす法で解いてます。