11106 操作（c）

经验值：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;
}