1798: [Ahoi2009]Seq 维护序列seq
Time Limit: 30 Sec Memory Limit: 64 MB
Submit: 5531 Solved: 1946
[Submit][Status][Discuss]
Description
老师交给小可可一个维护数列的任务，现在小可可希望你来帮他完成。 有长为N的数列，不妨设为a1,a2,…,aN 。有如下三种操作形式： (1)把数列中的一段数全部乘一个值; (2)把数列中的一段数全部加一个值; (3)询问数列中的一段数的和，由于答案可能很大，你只需输出这个数模P的值。
Input
第一行两个整数N和P(1≤P≤1000000000）。第二行含有N个非负整数,从左到右依次为a1,a2,…,aN, (0≤ai≤1000000000,1≤i≤N)。第三行有一个整数M，表示操作总数。从第四行开始每行描述一个操作，输入的操作有以下三种形式： 操作1：“1 t g c”(不含双引号)。表示把所有满足t≤i≤g的ai改为ai×c (1≤t≤g≤N,0≤c≤1000000000)。 操作2：“2 t g c”(不含双引号)。表示把所有满足t≤i≤g的ai改为ai+c (1≤t≤g≤N,0≤c≤1000000000)。 操作3：“3 t g”(不含双引号)。询问所有满足t≤i≤g的ai的和模P的值 (1≤t≤g≤N)。 同一行相邻两数之间用一个空格隔开，每行开头和末尾没有多余空格。
Output
对每个操作3，按照它在输入中出现的顺序，依次输出一行一个整数表示询问结果。
Sample Input
7 43
1 2 3 4 5 6 7
5
1 2 5 5
3 2 4
2 3 7 9
3 1 3
3 4 7
1 2 3 4 5 6 7
5
1 2 5 5
3 2 4
2 3 7 9
3 1 3
3 4 7
Sample Output
2
35
8
35
8
HINT
【样例说明】
初始时数列为(1,2,3,4,5,6,7)。
经过第1次操作后，数列为(1,10,15,20,25,6,7)。
对第2次操作，和为10+15+20=45，模43的结果是2。
经过第3次操作后，数列为(1,10,24,29,34,15,16}
对第4次操作，和为1+10+24=35，模43的结果是35。
对第5次操作，和为29+34+15+16=94,模43的结果是8。
测试数据规模如下表所示
数据编号 1 2 3 4 5 6 7 8 9 10
N= 10 1000 1000 10000 60000 70000 80000 90000 100000 100000
M= 10 1000 1000 10000 60000 70000 80000 90000 100000 100000
Solution
双标记线段树，与普通线段树类似，标记下传时考虑乘法即可。
/**************************************************************
Problem: 1798
User: shadowland
Language: C++
Result: Accepted
Time:4500 ms
Memory:40392 kb
****************************************************************/ #include "bits/stdc++.h" using namespace std ;
typedef long long QAQ ;
const int maxN = ;
struct SegTree { int l , r ; QAQ sum , mul , add ; } tr[ maxN ] ;
QAQ MOD , val ; QAQ arr[ maxN ] ; void Push_up ( const int i ) {
tr[ i ].sum = ( tr[ i << | ].sum + tr[ i << ].sum ) % MOD ;
} void Push_down ( int i , int m ) {
tr[ i << ].add = ( tr[ i << ].add * tr[ i ].mul + tr[ i ].add ) % MOD ;
tr[ i << | ].add = ( tr[ i << | ].add * tr[ i ].mul + tr[ i ].add ) % MOD ;
tr[ i << ].mul = tr[ i << ].mul * tr[ i ].mul % MOD ;
tr[ i << | ].mul = tr[ i << | ].mul * tr[ i ].mul % MOD ;
tr[ i << ].sum = ( tr[ i << ].sum * tr[ i ].mul + tr[ i ].add * ( m - ( m >> ) ) ) % MOD ;
tr[ i << | ].sum = ( tr[ i << | ].sum * tr[ i ].mul + tr[ i ].add * ( m >> ) ) % MOD ;
tr[ i ].add = ;
tr[ i ].mul = ;
} void Build_Tree ( const int x , const int y , const int i ) {
tr[ i ].l = x ; tr[ i ].r = y ;
tr[ i ].mul = ;
if ( x == y ) {
tr[ i ].sum = arr[ x ] ;
return ;
}
else {
int mid = ( x + y ) >> ;
Build_Tree ( x , mid , i << ) ;
Build_Tree ( mid + , y , i << | ) ;
Push_up ( i ) ;
}
} QAQ Query_Tree ( const int q , const int w , const int i ) {
if ( q <= tr[ i ].l && tr[ i ].r <= w ) {
return tr[ i ].sum % MOD ;
}
else {
Push_down ( i , tr[ i ].r - tr[ i ].l + ) ;
int mid = ( tr[ i ].l + tr[ i ].r ) >> ;
if ( q > mid ) return Query_Tree ( q , w , i << | ) % MOD;
else if ( w <= mid ) return Query_Tree ( q , w , i << ) % MOD ;
else return ( Query_Tree ( q , w , i << | ) + Query_Tree ( q , w , i << ) ) % MOD ;
Push_up ( i ) ;
}
} void Update_Tree ( int i , int q , int w , int _ ) {
if ( q <= tr[ i ].l && tr[ i ].r <= w ) {
if ( _ == ) {
tr[ i ].add = tr[ i ].add * val % MOD ;
tr[ i ].mul = tr[ i ].mul * val % MOD ;
tr[ i ].sum = tr[ i ].sum * val % MOD ;
}
else if ( _ == ) {
tr[ i ].add = ( tr[ i ].add + val ) % MOD ;
tr[ i ].sum = ( tr[ i ].sum + ( QAQ ) val * ( tr[ i ].r - tr[ i ].l + ) ) % MOD ;
}
}
else {
Push_down ( i , tr[ i ].r - tr[ i ].l + ) ;
int mid = ( tr[ i ].l + tr[ i ].r ) >> ;
if ( q > mid ) Update_Tree ( i << | , q , w , _ ) ;
else if ( w <= mid ) Update_Tree ( i << , q , w , _ ) ;
else {
Update_Tree ( i << | , q , w , _ ) ;
Update_Tree ( i << , q , w , _ ) ;
}
Push_up ( i ) ;
}
} void DEBUG_( int n ) {
for ( int i= ; i<=n ; ++i ) {
printf ( "\n%d:\nsum:%d\nadd:%d\nmul:%d\n" , i , tr[ i ].sum , tr[ i ].add , tr[ i ].mul ) ;
}
}
int main ( ) {
QAQ N , Q ;
//freopen ( "sbsbs.out" , "w" , stdout ) ;
scanf ( "%lld %lld" , &N , &MOD ) ;
for ( int i= ; i<=N ; ++i ) scanf ( "%lld" , arr + i ) ;
Build_Tree( , N , ) ;
scanf ( "%lld" , &Q ) ;
for ( int i= ; i<=Q ; ++i ){
QAQ op , l , r ;
scanf ( "%lld" , &op ) ;
//DEBUG_( 13 ) ;
if ( op == ) {
scanf ( "%lld %lld" , &l , &r ) ;
printf ( "%lld\n" , Query_Tree ( l , r , ) ) ;
}
else {
scanf ( "%lld %lld %lld" , &l , &r , &val ) ;
Update_Tree ( , l , r , op ) ;
}
}
return ;
}
2016-10-13 22:15:31
(完)