問題一覧 > 通常問題

No.3208 Parse AND OR Affection

レベル : / AI推定難易度 : 1825 / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 28
作問者 : amesyu / テスター : noshinn lmorinn 👑 qand
お気に入りにしたユーザー ProblemId : 12326 / 自分の提出
問題文最終更新日: 2025-07-18 15:55:34
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 474 (順位表) の他の問題:

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
Expressions are evaluated left-associatively. For example, 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 is T.
  • 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.
On the other hand, the following strings are not logic gate expressions.
  • FFT
  • C+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もしくは右上の雲マークをクリックしてアカウントを作成してください。