Seq 维护序列seq

Time Limit: 30 Sec  Memory Limit: 64 MB

Submit: 4184  Solved: 1518

[][][]

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

Sample Output

2

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

题解：给两个操作，操作1，把l,r数字乘以c，操作2：把l,r数字都加上c；

直接开两个标记去存储，样例过了，但是无限wa；

我有几点没考虑完全：

1：对于第一个操作，每次标记应该都是乘以c；而我弄成加了，因为假设第一次乘以5，第二次再乘以5，就是25

了；

2：对于第二种操作，没有考虑到第一种操作可以影响第二种操作，如果执行第一种操作，里面的元素编程5倍了，此时标记2也应当乘以相应倍数；加上5+2，5乘以5了，2也应当乘以5；

总结：考虑问题还是不太全面，不能完全驾驭题目；

代码：

1 extern "C++"{  2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #include
          
             7 #include
           
             8 #include
            
              9 using namespace std; 10 typedef long long LL; 11 typedef unsigned u; 12 typedef unsigned long long ull; 13 #define mem(x,y) memset(x,y,sizeof(x)) 14 void SI(double &x){scanf("%lf",&x);} 15 void SI(int &x){scanf("%d",&x);} 16 void SI(LL &x){scanf("%lld",&x);} 17 void SI(u &x){scanf("%u",&x);} 18 void SI(ull &x){scanf("%llu",&x);} 19 void SI(char *s){scanf("%s",s);} 20 21 void PI(int x){printf("%d",x);} 22 void PI(double x){printf("%lf",x);} 23 void PI(LL x){printf("%lld",x);} 24 void PI(u x){printf("%u",x);} 25 void PI(ull x){printf("%llu",x);} 26 void PI(char *s){printf("%s",s);} 27 28 #define NL puts(""); 29 #define ll root<<1 30 #define rr root<<1|1 31 #define lson ll,l,mid 32 #define rson rr,mid+1,r 33 const int INF=0x3f3f3f3f; 34 const int MAXN=100010; 35 LL tree[MAXN << 2]; 36 LL lazy[MAXN << 2]; 37 LL lazy2[MAXN << 2]; 38 LL P; 39 } 40 void pushup(int root){ 41 tree[root] = tree[ll] + tree[rr]; 42 tree[root] %= P; 43 } 44 void pushdown(int root,int x){ 45 if(lazy[root] != 1){ 46 lazy[ll] *= lazy[root]; 47 lazy[rr] *= lazy[root]; 48 49 lazy2[ll] *= lazy[root]; 50 lazy2[rr] *= lazy[root]; 51 // tree[ll]=lazy[root]*(mid-l+1); 52 // tree[rr]=lazy[root]*(r-mid); 53 tree[ll] *= lazy[root]; 54 tree[rr] *= lazy[root]; 55 56 lazy[ll] %= P; 57 lazy[rr] %= P; 58 tree[ll] %= P; 59 tree[rr] %= P; 60 lazy2[ll] %= P; 61 lazy2[rr] %= P; 62 63 lazy[root] = 1; 64 } 65 if(lazy2[root]){ 66 lazy2[ll] += lazy2[root]; 67 lazy2[rr] += lazy2[root]; 68 69 lazy2[ll] %= P; 70 lazy2[rr] %= P; 71 72 tree[ll] += lazy2[root] * (x - (x >> 1) ) % P; 73 tree[rr] += lazy2[root] * (x >> 1) % P; 74 75 tree[ll] %= P; 76 tree[rr] %= P; 77 78 lazy2[root] = 0; 79 } 80 } 81 void build(int root,int l,int r){ 82 int mid = (l + r) >> 1; 83 lazy[root] = 1; 84 lazy2[root] = 0; 85 if(l == r){ 86 SI(tree[root]); 87 return ; 88 } 89 build(lson); 90 build(rson); 91 pushup(root); 92 } 93 void update(int root,int l,int r,int L,int R,int C,int t){ 94 if(l >= L && r <= R){ 95 if(t == 1){ 96 lazy[root] *= C; 97 tree[root] *= C; 98 lazy2[root] *= C; 99 lazy2[root] %= P;100 lazy[root] %= P;101 tree[root] %= P;102 }103 else if(t == 2){104 lazy2[root] += C % P;105 tree[root] += C * (r - l +1) % P;106 lazy2[root] %= P;107 tree[root] %= P;108 }109 return ;110 }111 int mid = (l + r) >> 1;112 pushdown(root,r - l + 1);113 if(mid >= L)114 update(lson,L,R,C,t);115 if(mid < R)116 update(rson,L,R,C,t);117 pushup(root);118 }119 LL query(int root,int l,int r,int L,int R){120 int mid = (l + r) >> 1;121 if(l >= L && r <= R){122 return tree[root];123 }124 pushdown(root,r - l + 1);125 LL ans = 0;126 if(mid >= L)127 ans += query(lson,L,R);128 if(mid < R)129 ans += query(rson,L,R);130 return ans;131 }132 int main(){133 // assert(true);134 int N,M;135 while(~scanf("%d%lld",&N,&P)){136 build(1,1,N);137 SI(M);138 int a,l,r,c;139 while(M--){140 SI(a);SI(l);SI(r);141 if(a == 3){142 printf("%lld\n",query(1,1,N,l,r) % P);143 }144 else{145 SI(c);146 update(1,1,N,l,r,c,a);147 }148 }149 }150 return 0;151 }