首页 > 其他 > 详细

牛客小白月赛5 I 区间 (interval)

时间:2018-07-23 19:32:26      阅读:162      评论:0      收藏:0      [点我收藏+]

题意:中文题

思路:这个题当时搞了一发爆了内存,最初以为是线段树裸题,搞了就爆了内存,然后用类似于莫队一样的算法搞了一发,通过率很低,看了其他人的代码才知道,这其实是一个类似于前缀和一样的东西,我通过记录前缀的加和,最后来确定我进行了多少修改,挺巧妙的

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=1e6+6;
int a[maxn],pre[maxn];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=m;i++){
        int op,l,r,val;
        scanf("%d%d%d%d",&op,&l,&r,&val);
        if(op==1)val=-val;
        pre[l]+=val;pre[r+1]-=val;
    }
    LL sum=0;
    for(int i=1;i<=n;i++){
        sum+=pre[i];
        a[i]+=sum;
    }
    sum=0;
    int l,r;
    scanf("%d%d",&l,&r);
    for(int i=l;i<=r;i++){
        sum+=a[i];
//        printf("fuck\n");
    }
    printf("%lld\n",sum);
    return 0;
}

 

牛客小白月赛5 I 区间 (interval)

原文:https://www.cnblogs.com/lalalatianlalu/p/9356358.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!