解法
時刻tに学生mがログインしているかどうかだけが知りたいため、実はPCの何番目がログインされているかどうか、という情報は特に必要ありません。
まずはいもす法を用いて下準備をします。
memo[i][j] = 学生iが時刻jに何台のPCでログインしているか、という情報を記録することにすると、
時刻xに学生yがログインしたときはmemo[y][x]に+1を、ログアウトしたときはmemo[y][x+1]に-1をしてあげた上で、すべての記録を入力し終えた後で、時刻0からの累積和を取ってあげれば、上の情報がうまく格納されます。
次に、sum[i][j] = 学生iがスタート時刻から時刻jまでに何分間ログインしていたか、という情報をいれることにします。
これは、
memo[i][j]が1以上
sum[i][j] = sum[i][j-1]+1memo[i][j]が0
sum[i][j] = sum[i][j-1]
として累積和を取っていくと、うまく記録できます。
最後にクエリにこたえていきます。
学生mの、時刻xから時刻yまでのログイン時間は、
sum[m][y-1] - sum[m][x-1]
で求めることができます。
