「4.3」维护序列

「4.3」维护序列

问题背景

「一本通4.3 练习3」

题目描述

老师交给小可可一个维护数列的任务，现在小可可希望你来帮他完成。

有长为 n 的数列，不妨设为 a[1],a[2],… ,a[n] 。有如下三种操作形式：

　　把数列中的一段数全部乘一个值；
　　把数列中的一段数全部加一个值；
　　询问数列中的一段数的和，由于答案可能很大，你只需输出这个数模 P 的值。

输入格式

第一行两个整数 n 和 P；
第二行含有 n 个非负整数，从左到右依次为 a[1],a[2],… ,a[n]；
第三行有一个整数 M，表示操作总数；

从第四行开始每行描述一个操作，输入的操作有以下三种形式：

　　操作 1：1 t g c，表示把所有满足 t≤i≤g 的 a[i] 改为 a[i]×c；
　　操作 2：2 t g c，表示把所有满足 t≤i≤g 的 a[i] 改为 a[i]+c；
　　操作 3：3 t g，询问所有满足t≤i≤g 的 a[i] 的和模 P 的值。

同一行相邻两数之间用一个空格隔开，每行开头和末尾没有多余空格。

输出格式

对每个操作 3，按照它在输入中出现的顺序，依次输出一行一个整数表示询问结果。

样例输入1

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
35
8

注释说明

样例说明

初始时数列为 {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≤t≤g≤n,  0≤c,a[i]≤10^9,   1≤P≤10^9。

数据点1：n=10, M=10
数据点2,3：n=10^3, M=10^3
数据点4：n=10^4, M=10^4
数据点5：n=6×10^4, M=6×10^4
数据点6：n=7×10^4, M=7×10^4
数据点7：n=8×10^4, M=8×10^4
数据点8：n=9×10^4, M=9×10^4
数据点9,10：n=10^5, M=10^5

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+1;
char op[5];
int n,w[N],p,m;
struct tree{int l,r;ll sum,add,mul;
}a[N<<2];
void pushup(int k){a[k].sum=(a[k<<1].sum+a[k<<1 | 1].sum)%p;
}
void build(int k,int l,int r){a[k]=(tree){l,r,0,0,1};if(l==r){a[k].sum=w[l];return ;}int mid=l+r >>1;build(k<<1,l,mid);build(k<<1 | 1 ,mid+1,r);pushup(k);
}
void calc(tree &k,int jj,int cc){k.sum=(ll)k.sum*cc%p+(ll)(k.r-k.l+1)*jj%p;k.mul=(ll)k.mul*cc%p;k.add=((ll)k.add*cc+jj)%p;
}
void pushdown(int k){calc(a[k<<1],a[k].add ,a[k].mul );calc(a[k<<1 | 1],a[k].add ,a[k].mul );a[k].add=0;a[k].mul=1;
}
void update(int k,int l,int r,int aa,int mm){if(l<=a[k].l&&r>=a[k].r ){calc(a[k],aa,mm);return;}pushdown(k);int mid=a[k].l+a[k].r>>1;if(l<=mid)update(k<<1,l,r,aa,mm);if(r>=1+mid)update(k<<1 | 1,l,r,aa,mm);pushup(k);
}
int query(int k,int l,int r){if(l<=a[k].l&&a[k].r<=r)return a[k].sum;pushdown(k);int res=0;int mid=a[k].l+a[k].r>>1;if(mid>=l)res=query(k<<1,l,r)%p;if(r>mid)res+=query(k<<1 | 1,l,r)%p;return res%p;
}
int main(){scanf("%d%d",&n,&p);for(int i=1;i<=n;i++)scanf("%d",&w[i]);build(1,1,n);scanf("%d",&m);while(m--){int t,g,c;scanf("%s%d%d",op,&t,&g);if(op[0]=='1'){scanf("%d",&c);update(1,t,g,0,c);}else if(op[0]=='2'){scanf("%d",&c);update(1,t,g,c,1);}else {printf("%d\n",query(1,t,g));}}
}

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n, m, p;
int w[N];
struct tree {int l, r;LL sum, add, mul;
} tr[N << 2];void pushup(int u) {tr[u].sum = (tr[u << 1].sum + tr[u << 1 | 1].sum) % p;
}//乘：calc(1, 0, c)，加：calc(1, c, 1)
void calc(tree &k, int jia, int cheng) {k.sum = ((LL) k.sum * cheng + (LL) (k.r - k.l + 1) * jia) % p;k.mul = (LL) k.mul * cheng % p;k.add = ((LL) k.add * cheng + jia) % p;
}void pushdown(int k) {//if(tr[k].add!=0 && tr[k].mul!=1) {calc(tr[k << 1], tr[k].add, tr[k].mul);calc(tr[k << 1 | 1], tr[k].add, tr[k].mul);//}// 清空懒标记tr[k].add = 0, tr[k].mul = 1;
}
void build(int k, int l, int r) {tr[k]= (tree){l,r,0,0,1}; //初始化，后面通过pushup去更新if (l == r) {tr[k] = (tree){l, r, w[l], 0, 1};return ;}int mid = l + r >> 1;build(k << 1, l, mid);build(k << 1 | 1, mid + 1, r);pushup(k);
}void update(int k, int l, int r, int add, int mul) {if (l <= tr[k].l && tr[k].r <= r) {calc(tr[k], add, mul);return;}pushdown(k);int mid = tr[k].l + tr[k].r >> 1;if (l <= mid) update(k << 1, l, r, add, mul);if (r >= mid+1) update(k << 1 | 1, l, r, add, mul);pushup(k);
}int query(int k, int l, int r) {if (l <= tr[k].l && tr[k].r <= r) return tr[k].sum;pushdown(k);int res = 0;int mid = tr[k].l + tr[k].r >> 1;if (l <= mid) res += query(k << 1, l, r);if (r > mid) res = (res + query(k << 1 | 1, l, r)) % p;return res;
}
int main() {scanf("%d%d", &n, &p);for (int i = 1; i <= n; i++) scanf("%d", &w[i]);build(1, 1, n);scanf("%d", &m);while (m--) {int op, t, g, c;scanf("%d%d%d", &op, &t, &g);if (op != 3) scanf("%d",&c);//把a[i]改为a[i]*c（加上0，乘以c）if (op == 1) update(1, t, g, 0, c);//把a[i]改成a[i]+c （加上c，乘以1）else if (op == 2) update(1, t, g, c, 1);//查询所有满足情况的值else printf("%d\n", query(1, t, g),);}return 0;
}