蒟蒻KC的垃圾数列

向右看齐 2021-10-26 12:44 181阅读 0赞

## 题目背景 ##

在某教练的强迫之下，我一个蒟蒻居然出题了！！！出题了！！！（数据太水别找我qwq）

好的，JL说好的一题100快拿来

## 题目描述 ##

首先，给你一个空的长度为n的序列（废话）

然后，你有一系列神奇操作，好吧好吧，只有一个，那就是：

L R K D：给出一个长度等于R-L+1的等差数列，首项为K，公差为D，并将它对应加到a\[L\]~a\[R\]的每一个数上。即：令a\[L\]=a\[L\]+K，a\[L+1\]=a\[L+1\]+K+D（假装没有抄袭洛谷P1438题面）

这个操作有m次。

我还要问你q个问题：（当然，是在m次操作之后）

即前1个，2个……q个数的和。（答案可能太大，请输出ans%（10^9+7））

## 输入格式 ##

第一行两个整数数n，m，q，表示数列长度和操作个数。 接下来的m行，表示操作，即 L R K D

## 输出格式 ##

对于每个询问，输出答案，每个答案占一行。（也就是q行，答案%（10^9+7））

## 输入输出样例 ##

### 输入 \#1 ###

5 2 5
    2 3 4 5
    2 4 1 2

### 输出 \#1 ###

0
    5
    17
    22
    22

## 说明/提示 ##

样例最后序列为0 5 12 5 0

## 数据范围： ##

0%是 样例（别打表）

30% 0<=n<=10000,0<=m<=10000

60% 0<=n<=100000,0<=m<=100000

100% 0<=n<=10000000,0<=m<=10000000

100%数据满足 0<=q<=min(n,1000000)

毒瘤出题人，暴力能拿60.。。。。。

#include<cstdio>
    
    using namespace std;
    
    const int MOD=1000000007;
    
    const int Q=2000005;
    
    int a[Q],b[Q],n,m,q,i,l,r,k,d;
    
    long long ans=0;
    
    inline int read(){
        int s=0,w=1;
        char ch=getchar();
        while(ch<'0'||ch>'9'){
            if(ch=='-'){
                w=-1;
            }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            s=s*10+ch-'0';
            ch=getchar();
        }
        return s*w;
    }
    
    int main(){
        n=read();
        m=read();
        q=read();
        for(i=1;i<=m;i++){
            int x,y;
            l=read();
            r=read();
            k=read();
            d=read();
            x=l+1;
            y=r+1;
            a[l]+=k;
            a[l]%=MOD;
            a[y]-=k+(r-l)*d;
            b[x]+=d;
            b[x]%=MOD;
            b[y]-=d;
        }
        for(i=1;i<=q;i++){
            b[i]+=b[i-1];
            b[i]%=MOD;
        }
        for(i=1;i<=q;i++){
            a[i]+=b[i];
            a[i]%=MOD;
        }
        for(i=1;i<=q;i++){
            a[i]+=a[i-1];
            a[i]%=MOD;
        }
        for(i=1;i<=q;i++){
            ans+=a[i]%MOD;
            ans%=MOD;
            printf("%lld\n",ans);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/hrj1/p/11357192.html