首页 > 代码库 > homework

homework

2024-09-05 09:32:57   212人阅读

【题目描述】

老师给YouSiki布置了一项编程作业，但YouSiki昨天沉迷于买花的喜悦之中忘了做作业。所以YouSiki找到了你来帮她完成这项作业。

作业是这样的：给出一个n项的数字序列，有Q个操作。操作分为三种，一种是查询操作，包含两个参数l,r，表示询问区间l,r内的数字之和是多少；一种是加法操作，包含三个参数l,r,a，表示将区间l,r内的数字分别加上a；另一种是乘法操作，包含三个参数l,r,a，表示将区间l,r内的数字分别乘上a。

 

【输入格式】

第一行两个整数n,Q，含义见题目描述。

接下来一行n个整数，表示初始的数字序列。

接下来Q行，每行是一个操作，格式如下：

  1. Q l r     表示询问区间[l,r]内的数字和。
  2. A l r a    表示将区间[l,r]内的数字加上a。
  3. M l r a 表示将区间[l,r]内的数字乘上a。

 

【输出格式】

对于每个Q操作，你需要输出一个整数表示答案。因为答案可能很大，所以你只需要输出答案模1,000,000,007的结果即可。

 

【样例输入】

5 3

3 2 1 5 7

A 1 4 7

M 2 3 8

Q 2 5

 

【样例输出】

155

 

【数据规模与约定】

对于50%的数据，1≤n,Q≤1,000。

对于100%的数据，1≤n,Q≤300,000，输入数字均小于模数。

#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;const int maxn=300000,mod=1000000007;int n,m;int l[maxn<<2],r[maxn<<2];long long mul[maxn<<2],add[maxn<<2],sum[maxn<<2];void build(int p,int ll,int rr){    l[p]=ll;    r[p]=rr;    mul[p]=1;    add[p]=0;    if (ll==rr){        scanf("%lld",&sum[p]);        return;    }    int mid=(ll+rr)/2;    build(p<<1,ll,mid);    build(p<<1|1,mid+1,rr);    sum[p]=(sum[p<<1]+sum[p<<1|1])%mod;    return;}inline void down(int p){    if (mul[p]!=1){        (mul[p<<1]*=mul[p])%=mod;        (add[p<<1]*=mul[p])%=mod;        (sum[p<<1]*=mul[p])%=mod;                (mul[p<<1|1]*=mul[p])%=mod;        (add[p<<1|1]*=mul[p])%=mod;        (sum[p<<1|1]*=mul[p])%=mod;                mul[p]=1;    }    if (add[p]!=0){        (add[p<<1]+=add[p])%=mod;        (sum[p<<1]+=(r[p<<1]-l[p<<1]+1)*add[p])%=mod;                (add[p<<1|1]+=add[p])%=mod;        (sum[p<<1|1]+=(r[p<<1|1]-l[p<<1|1]+1)*add[p])%=mod;                add[p]=0;    }    return;}void inc(int p,int a,int b,int c){    if (l[p]>=a&&r[p]<=b){        add[p]+=c;        (sum[p]+=(long long)c*(r[p]-l[p]+1))%=mod;        return;    }    down(p);    int mid=(l[p]+r[p])/2;    if (a<=mid) inc(p<<1,a,b,c);    if (b>mid) inc(p<<1|1,a,b,c);    sum[p]=(sum[p<<1]+sum[p<<1|1])%mod;    return;}void mult(int p,int a,int b,int c){    if (l[p]>=a&&r[p]<=b){        (add[p]*=c)%=mod;        (mul[p]*=c)%=mod;        (sum[p]*=c)%=mod;        return;    }    down(p);    int mid=(l[p]+r[p])/2;    if (a<=mid) mult(p<<1,a,b,c);    if (b>mid) mult(p<<1|1,a,b,c);    sum[p]=(sum[p<<1]+sum[p<<1|1])%mod;    return;}int ask(int p,int a,int b){    if (r[p]<a||l[p]>b) return 0;    if (l[p]>=a&&r[p]<=b) return sum[p];    down(p);    return (ask(p<<1,a,b)+ask(p<<1|1,a,b))%mod;}char op[10];int main(){    int a,b,c;    freopen("homework.in","r",stdin);    freopen("homework.out","w",stdout);    scanf("%d%d",&n,&m);    build(1,1,n);    while(m--){        scanf("%s%d%d",op,&a,&b);        if (op[0]==‘Q‘) printf("%d\n",ask(1,a,b));        else{            scanf("%d",&c);            if (op[0]==‘A‘) inc(1,a,b,c);            else mult(1,a,b,c);        }    }    fclose(stdout);    return 0;}

 

homework


联系
我们