理解が追い付かなかったので記録メモです 
問題
ある期間におけるイベントの出席者数の総和を計算する
入力例
期間D、人数N、それぞれの出席期間が入力として与えられる
8 # 8日間
5 # 5人
2 3 # 1人目 (例：2~3日目まで参加)
3 6 # 2人目
5 7 # 3人目
3 7 # 4人目
1 5 # 5人目
出力例
1～8日間のそれぞれの出席人数を出力する
1 # 1日目
2 # 2日目
4 # 3日目
3 # 4日目
4 # 5日目
3 # 6日目
2 # 7日目
0 # 8日目
分かりやすく視覚化する
各イベント実施日について、スプレッドシートで総和を求めると以下のようになる
駄目だった解法
各実施日ごとに加算していくと、計算量が増えて制約条件を満たせない 
int D = int.Parse(Console.ReadLine());
int N = int.Parse(Console.ReadLine());
int[] L = new int[D];
int[] R = new int[D];
for (int i = 0; i < N; i++)
{
int[] list = Console.ReadLine().Split().Select(int.Parse).ToArray();
L[i] = list[0];
R[i] = list[1];
}
// 各実施日の出席者数を配列にする
int[] s = new int[D];
for (int i = 0; i < N; i++)
{
var nums = Enumerable.Range(L[i], (R[i] - L[i] + 1));
foreach (var num in nums)
{
s[num - 1] += 1;
}
}
foreach (var item in s)
{
Console.WriteLine(item);
}
差分配列を利用する解法
- 長さD+2の配列
diffを用意し、両端に番兵(ダミー要素)を設ける - 各参加者について、出席開始日に+1、出席終了日の翌日に-1を
diff配列に加算 -
diff配列の前から順に累積和を取ることで、各日の出席者数が求まる
int D = int.Parse(Console.ReadLine());
int N = int.Parse(Console.ReadLine());
int[] diff = new int[D + 2]; // 差分配列 (両端に番兵を設ける)
for (int i = 0; i < N; i++)
{
string[] input = Console.ReadLine().Split();
int Li = int.Parse(input[0]);
int Ri = int.Parse(input[1]);
diff[Li]++; // 出席開始日に+1
diff[Ri + 1]--; // 出席終了日の翌日に-1
}
int[] attendance = new int[D + 1]; // 各日の出席者数を格納する配列
int sum = 0;
for (int i = 1; i <= D; i++)
{
sum += diff[i]; // 差分配列の累積和を計算
attendance[i] = sum; // 出席者数を格納
Console.WriteLine(attendance[i]);
}
実行時間が全然違った
下に差分配列を追加。
参加開始日に +1、参加終了日の翌日に -1 とし、差分配列の累積和を取ることで元の配列が求まる
考え方としては、各実施日ごとに計算するのではなく増減（差分）に注目している 