No.3208 Parse AND OR Affection
Problem Statement
You are given a logic gate expression $X$ of length $N$, as defined below.
You are given $Q$ queries; process them in order. The $k$-th query is as follows.
- You are given positive odd integers $L_k, R_k$. Find the number of pairs of integers $(i, j)$ satisfying $L_k \leq i \leq j \leq R_k$ such that the contiguous substring of $X$ from position $i$ to position $j$ can be interpreted as a logic gate expression and its value is
T.
Definition of Logic Gate Expressions
A string of odd length in which every odd-positioned character is one of TF and every even-positioned character is one of +*^ is called a logic gate expression.
T and F represent true and false respectively, and +*^ represent logical OR, logical AND, and exclusive OR respectively.
Here, the truth tables of logical OR, logical AND, and exclusive OR are as follows.
| A | B | A + B (OR) | A * B (AND) | A ^ B (XOR) |
|---|---|---|---|---|
| T | T | T | T | F |
| T | F | T | F | T |
| F | T | T | F | T |
| F | F | F | F | F |
F+T^T*F is interpreted as (((F+T)^T)*F), and its value is F.For example, the following strings are logic gate expressions.
T: its value isT.F+F*T: its value is((F+F)*T) = (F*T) = F.T^F+T^F*T: its value is((((T^F)+T)^F)*T) = T.
FFTC+T+F+T^T+^^
Constraints
- $1 \leq N \leq 252525$
- $N$ is odd
- $1 \leq Q \leq 10^5$
- $|X| = N$
- $X$ can be interpreted as a logic gate expression
- $1 \leq L_k \leq R_k \leq N$
- $L_k, R_k$ are odd
Input
$N$ $Q$ $X$ $L_1$ $R_1$ $L_2$ $R_2$ $\vdots$ $L_Q$ $R_Q$
Output
On the $k$-th line, output the answer to the $k$-th query.
Sample
Sample 1
Input
9 4 T^T+F^T*T 3 7 1 9 1 3 5 5
Output
4 10 2 0
In the first query, the contiguous substrings that are logic gate expressions and their values are as follows.
T = T, F = F, T = T, T+F = T, F^T = T, T+F^T = F
Therefore, the number of those whose value is T is $4$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。