?

Description

老師交給小可可一個(gè)維護(hù)數(shù)列的任務(wù)，現(xiàn)在小可可希望你來(lái)幫他完成。 有長(zhǎng)為N的數(shù)列，不妨設(shè)為a1,a2,…,aN 。有如下三種操作形式： (1)把數(shù)列中的一段數(shù)全部乘一個(gè)值; (2)把數(shù)列中的一段數(shù)全部加一個(gè)值; (3)詢問(wèn)數(shù)列中的一段數(shù)的和，由于答案可能很大，你只需輸出這個(gè)數(shù)模P的值。

Input

第一行兩個(gè)整數(shù)N和P(1≤P≤1000000000）。第二行含有N個(gè)非負(fù)整數(shù),從左到右依次為a1,a2,…,aN, (0≤ai≤1000000000,1≤i≤N)。第三行有一個(gè)整數(shù)M，表示操作總數(shù)。從第四行開始每行描述一個(gè)操作，輸入的操作有以下三種形式： 操作1：“1 t g c”(不含雙引號(hào))。表示把所有滿足t≤i≤g的ai改為ai×c (1≤t≤g≤N,0≤c≤1000000000)。 操作2：“2 t g c”(不含雙引號(hào))。表示把所有滿足t≤i≤g的ai改為ai+c (1≤t≤g≤N,0≤c≤1000000000)。 操作3：“3 t g”(不含雙引號(hào))。詢問(wèn)所有滿足t≤i≤g的ai的和模P的值 (1≤t≤g≤N)。 同一行相鄰兩數(shù)之間用一個(gè)空格隔開，每行開頭和末尾沒有多余空格。

Output

對(duì)每個(gè)操作3，按照它在輸入中出現(xiàn)的順序，依次輸出一行一個(gè)整數(shù)表示詢問(wèn)結(jié)果。

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

Sample Output

2
35
8

HINT

【樣例說(shuō)明】

初始時(shí)數(shù)列為(1,2,3,4,5,6,7)。
經(jīng)過(guò)第1次操作后，數(shù)列為(1,10,15,20,25,6,7)。
對(duì)第2次操作，和為10+15+20=45，模43的結(jié)果是2。
經(jīng)過(guò)第3次操作后，數(shù)列為(1,10,24,29,34,15,16}
對(duì)第4次操作，和為1+10+24=35，模43的結(jié)果是35。
對(duì)第5次操作，和為29+34+15+16=94,模43的結(jié)果是8。



測(cè)試數(shù)據(jù)規(guī)模如下表所示

數(shù)據(jù)編號(hào) 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

線段樹的模板題,? 注意取模

1 //2018年2月22日12:28:56 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 using namespace std; 7 8 int n, m, mo; 9 int A[410000], B[410000], sum[410000], size[410000]; 10 11 void change(int k1){ 12 sum[k1] = (sum[k1*2]+sum[k1*2+1]) % mo; 13 } 14 15 void buildtree(int k1, int l, int r){ 16 size[k1] = r-l+1; B[k1] = 1; 17 if(l == r){ 18 scanf("%d", &sum[k1]); return; 19 } 20 int mid = (l+r) >> 1; 21 buildtree(k1*2, l, mid); 22 buildtree(k1*2+1, mid+1, r); 23 change(k1); 24 } 25 26 void add(int k1, int x){ 27 A[k1] = (A[k1]+x) % mo; 28 sum[k1] = (sum[k1]+1ll*size[k1]*x) % mo; 29 } 30 31 void chen(int k1, int x){ 32 A[k1] = 1ll*A[k1]*x % mo; 33 B[k1] = 1ll*B[k1]*x % mo; 34 sum[k1] = 1ll * sum[k1]*x % mo; 35 } 36 37 void pushdown(int k1){ 38 if(B[k1] != 1){ 39 chen(k1*2, B[k1]); 40 chen(k1*2+1, B[k1]); B[k1] = 1; 41 } 42 if(A[k1]){ 43 add(k1*2, A[k1]); 44 add(k1*2+1, A[k1]); 45 A[k1] = 0; 46 } 47 } 48 49 void add(int k1, int l, int r, int L, int R, int x){ 50 if(l>R || r<L) return; 51 if(l>=L && r<=R){ 52 add(k1, x); 53 return; 54 } 55 int mid = (l+r) >> 1; 56 pushdown(k1); 57 add(k1*2, l, mid, L, R, x); 58 add(k1*2+1, mid+1, r, L, R, x); 59 change(k1); 60 } 61 62 void chen(int k1, int l, int r, int L, int R, int x){ 63 if(l>R || r<L) return; 64 if(l>=L && r<=R){ 65 chen(k1, x); return; 66 } 67 int mid = l+r >> 1; 68 pushdown(k1); 69 chen(k1*2, l, mid, L, R, x); 70 chen(k1*2+1, mid+1, r, L, R, x); 71 change(k1); 72 } 73 74 int find(int k1, int l, int r, int L, int R){ 75 if(l>R || r<L) return 0; 76 if(l>=L && r<=R) return sum[k1]; 77 int mid = l+r >> 1; 78 pushdown(k1); 79 return (find(k1*2,l,mid,L,R) + find(k1*2+1,mid+1,r,L,R) ) % mo; 80 } 81 82 int main(){ 83 scanf("%d%d", &n, &mo); 84 buildtree(1, 1, n); 85 scanf("%d", &m); 86 for(; m; m--){ 87 int k1, k2, k3; 88 scanf("%d%d%d", &k1, &k2, &k3); 89 if(k1 == 2){ 90 int k4; scanf("%d", &k4); add(1, 1, n, k2, k3, k4); 91 }else if(k1 == 1){ 92 int k4; scanf("%d", &k4); chen(1, 1, n, k2, k3, k4); 93 }else printf("%d\n", find(1, 1, n, k2, k3)); 94 } 95 96 return 0; 97 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/sineagle/p/8458798.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ1798: [Ahoi2009]Seq 维护序列seq的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。