[COCI 2021/2022 #6] Palindromi

Luogu

IDLGP8406

Time1000ms

Memory512MB

DifficultyP6

2021回文自动机 PAMCOCI（克罗地亚）

给你一个长度为 $n$ 的 $\texttt{01}$ 序列，下标为 $1,2,\dots,n$。最初每个字符都代表了一个长度为 $1$ 的字符串。在一次连接中，需要选择两个字符串 $a$ 和 $b$，将它们删除后，换为字符串 $ab$，即在写下 $a$ 中的所有字符后写下字符串 $b$ 的所有字符。这 $n$ 个初始字符串需要用 $n-1$ 次连接操作连成一个字符串。第 $i$ 次选择的字符串用一个下标对 $(a_i,b_i)$ 描述，表示要连接的字符串是包含下标为 $a_i$ 的字符的和包含下标为 $b_i$ 的字符的。保证下标为 $a_i$ 和 $b_i$ 的字符不在同一字符串中。一些字符串 $w$ 的回文值被定义为 $w$ 中不同回文子串的个数。我们定义回文串为从左到右读和从右到左读相同的字符串。一个字符串的子串被定义为可以从字符串开头和（或）结尾开始删去一个或多个字符得到的字符串。对于每次连接操作，输出每次连成的字符串的回文值。 ## Input 第一行包含一个整数 $n$，表示字符个数。第二行一个长度为 $n$ 的 $01$ 字符串，表示初始字符串。接下来 $n-1$ 行，每行两个整数 $a_i$，$b_i$，表示第 $i$ 次连接操作。 ## Output 输出 $n-1$ 行，表示每次连接操作得到的字符串的回文值。 [samples] ## Note ### 样例解释3：在每个连接之后新创建的字符串是： $\tt 00, 10,00, 100, 1000,001000 $ 和 $\tt 00100010$。它们各自的回文值在样例输出中给出。例如 $\tt 00100010$ 的回文值是 $8$，因为字符串包含$8$回文子字符串： $\tt 0, 00, 000, 10001,0100010, 1010$ 和 $00100$。 ### 数据范围：对于 $9\%$ 的数据：$1\le n\le100$ 对于 $18\%$ 的数据：$1\le n\le1000$ 对于 $27\%$ 的数据：$a_i = 1, b_i = i + 1$ 对于 $100\%$ 的数据：$1\le n\le10^5$，$1\le a_i, b_i\le n$ 本题分值与 [COCI 2021-2022#6](https://hsin.hr/coci/contest6_tasks.pdf) 分值相同，满分 $110$ 分

Samples

Input #1

Output #1

2
3

Input #2

Output #2

Input #3

Output #3

API Response (JSON)

{
  "problem": {
    "name": "[COCI 2021/2022 #6]  Palindromi",
    "description": {
      "content": "给你一个长度为 $n$ 的 $\\texttt{01}$ 序列，下标为 $1,2,\\dots,n$。最初每个字符都代表了一个长度为 $1$ 的字符串。在一次连接中，需要选择两个字符串 $a$ 和 $b$，将它们删除后，换为字符串 $ab$，即在写下 $a$ 中的所有字符后写下字符串 $b$ 的所有字符。 这 $n$ 个初始字符串需要用 $n-1$ 次连接操作连成一个字符串。第 $i$ 次选择的字符",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8406"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给你一个长度为 $n$ 的 $\\texttt{01}$ 序列，下标为 $1,2,\\dots,n$。最初每个字符都代表了一个长度为 $1$ 的字符串。在一次连接中，需要选择两个字符串 $a$ 和 $b$，将它们删除后，换为字符串 $ab$，即在写下 $a$ 中的所有字符后写下字符串 $b$ 的所有字符。\n\n这 $n$ 个初始字符串需要用 $n-1$ 次连接操作连成一个字符串。第 $i$ 次选择的字符...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments