ACAC 题库 ac.isam.top
GitHub
AtCoder Beginner Contest 453
G
复制查询
Copy Query
AtCoder
⌀ 1735
原题
← E→

复制查询AI (CI翻译)

Problem Statement

题目描述

AI (CI翻译)

There are $N$ sequences of length $M$: $A_1,A_2,\dots,A_N$. Initially, all elements of all sequences are $0$. Hereafter, the $j$-th element of sequence $A_i$ is denoted by $A_{i,j}$.

有 $N$ 个长度为 $M$ 的序列：$A_1,A_2,\dots,A_N$。初始时，所有序列中的所有元素均为 $0$。 下文中，序列 $A_i$ 的第 $j$ 个元素记为 $A_{i,j}$。AI (CI翻译)

Process the following three types of queries in the given order, $Q$ queries in total.

按给定顺序处理总计 $Q$ 个以下三种类型的查询。AI (CI翻译)

  • Type $1$: Overwrite sequence $A_{X_i}$ with sequence $A_{Y_i}$. That is, for every integer $j$ ($1 \le j \le M$), change $A_{X_i,j}$ to $A_{Y_i,j}$.
  • Type $2$: Change the $Y_i$-th element of sequence $A_{X_i}$, that is, $A_{X_i,Y_i}$, to $Z_i$.
  • Type $3$: For sequence $A_{X_i}$, output the sum of elements from the $L_i$-th through the $R_i$-th, that is, $A_{X_i,L_i}+A_{X_i,L_i+1}+\dots+A_{X_i,R_i}$.
  • 类型 $1$：将序列 $A_{X_i}$ 覆盖为序列 $A_{Y_i}$。也就是说，对于每个整数 $j$（$1 \le j \le M$），将 $A_{X_i,j}$ 改为 $A_{Y_i,j}$。
  • 类型 $2$：将序列 $A_{X_i}$ 的第 $Y_i$ 个元素，即 $A_{X_i,Y_i}$，改为 $Z_i$。
  • 类型 $3$：输出序列 $A_{X_i}$ 中从第 $L_i$ 个到第 $R_i$ 个元素的和，即 $A_{X_i,L_i}+A_{X_i,L_i+1}+\dots+A_{X_i,R_i}$。
AI (CI翻译)

Constraints

约束条件

AI (CI翻译)
  • $1 \le N,M \le 2 \times 10^5$
  • $1 \le Q \le 2 \times 10^5$
  • Type $1$ queries satisfy the following constraints:
  • $1 \le X_i,Y_i \le N$
  • Type $2$ queries satisfy the following constraints:
  • $1 \le X_i \le N$
    • $1 \le Y_i \le M$
    • $0 \le Z_i \le 10^9$
  • Type $3$ queries satisfy the following constraints:
  • $1 \le X_i \le N$
    • $1 \le L_i \le R_i \le M$
  • All input values are integers.
  • $1 \le N,M \le 2 \times 10^5$
  • $1 \le Q \le 2 \times 10^5$
  • 类型 $1$ 查询满足以下约束：
  • $1 \le X_i,Y_i \le N$
  • 类型 $2$ 查询满足以下约束：
  • $1 \le X_i \le N$
    • $1 \le Y_i \le M$
    • $0 \le Z_i \le 10^9$
  • 类型 $3$ 查询满足以下约束：
  • $1 \le X_i \le N$
    • $1 \le L_i \le R_i \le M$
  • 输入中的所有数值均为整数。
AI (CI翻译)

Input

输入格式

AI (CI翻译)

The input is given from Standard Input in the following format:

输入通过标准输入给出，格式如下：AI (CI翻译)

N M Q
{\rm Query}_1
{\rm Query}_2
\vdots
{\rm Query}_Q

N M Q
{\rm Query}_1
{\rm Query}_2
\vdots
{\rm Query}_Q
AI (CI翻译)

Here, ${\rm Query}_i$ represents the $i$-th query.

其中，${\rm Query}_i$ 表示第 $i$ 个查询。AI (CI翻译)

A type $1$ query is given in the following format:

类型 $1$ 查询的格式如下：AI (CI翻译)

1 X_i Y_i

1 X_i Y_i
AI (CI翻译)

A type $2$ query is given in the following format:

类型 $2$ 查询的格式如下：AI (CI翻译)

2 X_i Y_i Z_i

2 X_i Y_i Z_i
AI (CI翻译)

A type $3$ query is given in the following format:

类型 $3$ 查询的格式如下：AI (CI翻译)

3 X_i L_i R_i

3 X_i L_i R_i
AI (CI翻译)

Output

输出格式

AI (CI翻译)

For each type $3$ query, output the answer to that query. If there are no type $3$ queries, the output should be empty.

对于每个类型 $3$ 查询，输出该查询的答案。如果没有类型 $3$ 查询，则输出为空。AI (CI翻译)

样例

Input #1
4 5 10
2 2 1 2
2 2 2 7
2 2 4 8
1 1 2
2 2 3 1
1 3 2
2 3 2 10
3 1 2 4
3 2 1 4
3 3 2 2
Output #1
15
18
10
In this input, prepare four sequences of length $5$. - In the $1$st query, set $A_{2,1}=2$. At this point, $A_2=(2,0,0,0,0)$. - In the $2$nd query, set $A_{2,2}=7$. At this point, $A_2=(2,7,0,0,0)$. - In the $3$rd query, set $A_{2,4}=8$. At this point, $A_2=(2,7,0,8,0)$. - In the $4$th query, overwrite sequence $A_1$ with sequence $A_2$. At this point, $A_1=(2,7,0,8,0)$. - In the $5$th query, set $A_{2,3}=1$. At this point, $A_2=(2,7,1,8,0)$. - In the $6$th query, overwrite sequence $A_3$ with sequence $A_2$. At this point, $A_3=(2,7,1,8,0)$. - In the $7$th query, set $A_{3,2}=10$. At this point, $A_3=(2,10,1,8,0)$. - In the $8$th query, output $A_{1,2}+A_{1,3}+A_{1,4}=7+0+8=15$. - In the $9$th query, output $A_{2,1}+A_{2,2}+A_{2,3}+A_{2,4}=2+7+1+8=18$. - In the $10$th query, output $A_{3,2}=10$.
题目信息
题号
abc453_g
所属比赛
AtCoder Beginner Contest 453
时间限制
2 s
内存限制
1024 MB

题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。