提供一种树状数组的做法。
对于每个操作，我们考虑求出它执行的次数。题目保证了对于操作 \(2\) 所执行的操作编号都比其自身编号小，换句话说，即每个操作的执行次数是由编号比它大的操作决定的。
有了这个性质后，不难发现可以倒着扫一遍每个操作。对于当前操作 \(i\)，可以通过前面的处理得到其执行的次数。如果是操作 \(1\)，直接更新 \(a\) 数组即可。如果是操作 \(2\)，则对执行操作的区间加上当前操作的次数即可（因为也要做相同的次数）。
现在我们需要一个东西来实现区间修改、单点查询。树状数组就是一个不错的选择。
时间复杂度 \(O(m\log m)\)，其中 \(m\) 为操作个数。
#include <iostream>
#include <cstdio>
#define MOD 10007
using namespace std;
int n,m,k,d,a[1000001],c,o[1000001],x[1000001],y[1000001];
int t[1000001];
int lowbit( int x )
{
return x & ( -x );
}
void update( int x , int y )
{
for( int i = x ; i <= m ; i += lowbit( i ) )
t[i] = ( ( t[i] + y ) % MOD + MOD ) % MOD;//注意这里可能会加上一个负数，因此需要特别处理。
}
int query( int x )
{
int sum = 0;
for( int i = x ; i >= 1 ; i -= lowbit( i ) )
sum = ( sum + t[i] ) % MOD;
return sum;
}
int main()
{
scanf( "%d%d%d" , &n , &m , &k );
for( int i = 1 ; i <= k ; i ++ )
scanf( "%d" , &c ),update( c , 1 ),update( c + 1 , -1 );//初始输入的操作都要执行一遍。
for( int i = 1 ; i <= m ; i ++ )
scanf( "%d%d%d" , &o[i] , &x[i] , &y[i] );
for( int i = m ; i >= 1 ; i -- )
{
if( o[i] == 1 ) a[x[i]] = ( a[x[i]] + query( i ) * y[i] % MOD ) % MOD;
if( o[i] == 2 ) d = query( i ),update( x[i] , d ),update( y[i] + 1 , -d );
}
for( int i = 1 ; i <= n ; i ++ )
printf( "%d " , a[i] );
return 0;
}