#P6934. ⽪卡丘

    ID: 6765 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2400提高+/省选-Trie模逆元贡献法增量维护

⽪卡丘

题目描述

最初有一棵只有根节点的二叉树。每经过一秒,每个已有节点会补齐缺失的左、右儿子。新产生的节点从下一秒起才产生儿子。

需要依次执行两种操作。

  • G T:让时间前进 TT 秒。
  • A S:从根节点按非空字符串 SS 移动。L 表示走向左儿子,R 表示走向右儿子。保证路径上的节点都存在。删除最终到达的节点及其整棵子树。此操作不推进时间。

对每个操作,输出操作完成后的树上节点数对 998244353998244353 取模的结果。

输入格式

第一行一个整数 tt,表示数据组数。

每组先输入一行一个整数 nn,表示操作数。接下来 nn 行,每行为 G T 或 A S。

输出格式

每次操作后输出一行一个整数,按输入次序共输出 ∑n\sum n 行。

样例

2
6
G 1
A L
G 1
A R
G 1
G 1
3
G 3
A LR
A RRR
3
2
5
2
5
11
15
12
11

数据范围

对于全部数据,1≤t≤1051\le t\le10^5,t≤∑n≤106t\le\sum n\le10^6,∑∣S∣,∑T≤106\sum |S|,\sum T\le10^6。这些求和覆盖整个输入。若没有攻击操作,则 ∑∣S∣=0\sum |S|=0。

原题数据占比 附加限制
前 20% t≤10t\le10,每组 $1\le n,\sum
另有 10% 只有 G 操作
每组内任一攻击路径 SS 都不是另一条攻击路径的前缀
另有 30% t≤∑n≤105t\le\sum n\le10^5,$\sum

原题时间限制 1 秒,内存限制 512 MB。

原 PDF 题面