2xN Tiling with Queries
Time limit2sMemory limit256 MB
Maintain the count of tilings of a 2xN grid by 1x2 and 2x1 tiles while cells get blocked and unblocked by queries.
- Level
Hard8 of 10
- Topics
- Dynamic programming, Segment tree, Matrix, Combinatorics
- Solved
- No attempts yet
Problem
Counting the ways to fill a 2xN rectangle with 1x2 or 2x1 tiles is a well-known problem.
A 2xN rectangle starts with no restrictions. Restrictions on cells where a block may not be placed appear and disappear repeatedly. Write a program that finds the number of ways to fill all cells except the restricted ones.
Each query is one of the following.
- 1 x y : Add a restriction that no block may be placed at position (x,y). It is guaranteed that there was no restriction there before.
- 2 x y : Remove the restriction that no block may be placed at position (x,y). It is guaranteed that there was a restriction there before.
Input
The first line gives N and the integer Q, the number of queries, separated by a space. (1 ≤ N ≤ 10^5, 1 ≤ Q ≤ 2 x 10^5)
Q lines follow, starting from the second line, each giving one of the two kinds of queries. Each query has the form t x y, with 1 ≤ t, x ≤ 2 and 1 ≤ y ≤ N.
Output
Print Q lines. On line i, print the number of ways after applying the first i queries, modulo (10^9 + 7).