QOJ.ac

QOJ

Time Limit: 1.5 s Memory Limit: 128 MB Total points: 100

#9088. 谁的梦

Statistics

定义一个序列的权值为不同数字的个数,例如 $[1,2,3,3]$ 权值为 $3$。

现在有 $n$ 个序列,我们在每个序列里面选一个连续非空子串,拼接起来,求所有选法得到的序列的权值之和。

如果一个序列能通过多种方法被选择出来,那么计算多次。

本题带修改操作,格式请参考输入格式。

由于结果可能过大,请输出答案 $\bmod 19260817$ 的结果。

输入格式

第一行两个整数 $n,m$,表示有 $n$ 个序列,$m$ 次修改。

第二行 $n$ 个整数,第 $i$ 个数是 $len_i$,表示第 $i$ 个序列的长度。

之后 $n$ 行,每行 $len_i$ 个整数,表示第 $i$ 个序列。

之后 $m$ 行,每行三个整数 $x,y,z$ 表示将第 $x$ 个序列的第 $y$ 个元素改为 $z$。

输出格式

输出 $m + 1$ 行,每行一个整数,依次表示初始局面以及每次修改后的答案。

样例数据

样例输入

2 5
6 6
1 3 1 1 3 2 
2 3 3 2 1 1 
1 1 1
1 1 2
1 1 2
1 1 1
1 1 1

样例输出

1158
1158
1168
1168
1158
1158

子任务

Idea:nzhtl1477,Solution:nzhtl1477,Code:nzhtl1477,Data:nzhtl1477( partially uploaded )

$1 \leq n,m,len_i \leq 10^5$,序列中的元素均为 $32$ 位整型数,$\sum len_i \leq 10^5$。

共 $50$ 组数据。

About Issues

We understand that our problem archive is not perfect. If you find any issues with the problem, including the statement, scoring configuration, time/memory limits, test cases, etc.

You may use this form to submit an issue regarding the problem. A problem moderator will review your issue and proceed it properly.

STOP! Before you submit an issue, please READ the following guidelines:

  1. This is not a place to publish a discussion, editorial, or requests to debug your code. Your issue will only be visible by you and problem moderators. Other users will not be able to view or reply your issues.
  2. Do not submit duplicated issues. If you have already submitted one, please wait for an moderator to review it. Submitting multiple issues will not speed up the review process and might cause your account to be banned.
  3. Issues must be filed in English or Chinese only.
  4. Be sure your issue is related to this problem. If you need to submit an issue regarding another problem, contest, category, etc., you should submit it to the corresponding page.

Active Issues 0

No issues in this category.

Closed/Resolved Issues 0

No issues in this category.