经验值：2000
时间限制：1000毫秒
内存限制：512MB
安徽省2024年信息学竞赛试题(初中组)
不许抄袭，一旦发现，直接清空经验！
题目描述 Description
小可可有一个长度为 nn 的初始都为 00 的数组和从左到右的 mm 个机器，每个机器 ii 都有两种类别之一。若机器 ii 是第一种机器，那么它需要执行的操作是将 axiaxi 的值加上 yiyi；如果机器 ii是第二种机器，那么它需要执行的操作是依次执行第 lili 到第 riri 个机器的操作，其中有 ri<iri<i。
需要注意的是，每个第二种机器只会执行它左边机器的操作。现在小可可依次执行了机器 c1c1, c2c2, …, ckck的操作，想知道最后得到的数组是什么。
由于数组中的元素可能很大，你只需要帮她求出每个元素除以 1000710007 的余数即可。
输入描述 Input Description
第一行三个正整数nn，mm和kk。
接下来一行kk个正整数，表示序列cc。
接下来mm行，每行三个正整数，第一个正整数oi∈{1,2}oi∈{1,2}，表示机器ii的类型。如果o=1o=1，则接下来两个正整数xixi,yiyi，1≤xi≤n1≤xi≤n，1≤yi≤1041≤yi≤104。如果o=2o=2，则接下来两个正整数lili,riri，1≤li≤ri<i1≤li≤ri<i。
输出描述 Output Description
一行nn个正整数，表示数组中每个元素除以1000710007的余数
样例输入 Sample Input
2 3 3 1 2 3 1 1 2 2 1 1 2 1 2
样例输出 Sample Output
8 0
数据范围及提示 Data Size & Hint
样例1解释:
先执行第一个机器的操作，给a1a1加上了22。
然后执行第二个机器的操作，它操作了第一个机器，给a1a1加上了22。
然后执行第三个机器的操作，它先操作了第一个机器，给a1a1加上了22，然后操作了第二个机器。第二个机器又操作了第一个机器，给a1a1加上了22。
所以最后a1=8a1=8,a2=0a2=0
数据规模与约定
对于10%10%的数据，1≤n,m,k≤101≤n,m,k≤10。
对于30%30%的数据，1≤n,m,k≤10001≤n,m,k≤1000。
对于另20%20%的数据，n=1n=1。
对于另20%20%的数据，k=1k=1。
对于100%100% 的数据，1≤n,m,k≤2×1051≤n,m,k≤2×105。
#include<bits/stdc++.h>
using namespace std;
int n,m,k,mod=10007;
int a[100005];
int o[100005];
int x[100005];
int y[100005];
int c;
int t[100005];
int main(){
cin>>n>>m>>k;
for(int i=1;i<=k;i++){cin>>c;t[c]++;
}
for(int i=1;i<=m;i++){cin>>o[i]>>x[i]>>y[i];
}
for(int i=n;i>=1;i--){if(o[i]==1){a[x[i]]=(a[x[i]]+y[i]*t[i])%mod;}else{for(int j=x[i];j<=y[i];j++){t[j]=(t[i]+t[j])%mod;}}
}
for(int i=1;i<=n;i++){cout<<a[i]<<" ";
}
return 0;
}
)
