加入收藏 | 设为首页 | 会员中心 | 我要投稿 李大同 (https://www.lidatong.com.cn/)- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置: 首页 > 百科 > 正文

cogs 1317. 数列操作C 区间修改 区间查询

发布时间:2020-12-16 10:47:07 所属栏目:百科 来源:网络整理
导读:1317. 数列操作C ★★★?? 输入文件: shuliec.in ?? 输出文件: shuliec.out ??? 简单对比 时间限制:1 s?? 内存限制:128 MB 【题目描述】 假设有一个长度为? n ( n ≤ 100000 ) ?的数列? A ,支持如下两种操作: 1. 将? A i , A i + 1 , … , A j ?的值均

1317. 数列操作C

★★★?? 输入文件:shuliec.in?? 输出文件:shuliec.out???简单对比
时间限制:1 s?? 内存限制:128 MB

【题目描述】

假设有一个长度为?n(n100000)?的数列?A,支持如下两种操作:

1. 将?Ai,Ai+1,,Aj?的值均增加?d

2. 查询?As+As+1+?+At(st)?的值。

根据操作要求进行正确操作并输出结果。

【输入格式】

第一行为一个正整数?n,表示数列的大小。

第二行有?n?个整数,表示数列?A?各项的初始值。

第三行为一个整数?m?,表示操作的个数。

下面是?m?行,每行描述一个操作:

ADD i j d(将?Ai,Ai+1,,Aj(1i,jn)?的值均增加一个整数?d

SUM s t(表示查询?As+?+At?的值)

【输出格式】

对于每一次询问,输出查询到的结果。

【样例输入】

4
1 4 2 3
3
SUM 1 3
ADD 2 2 50
SUM 2 3

【样例输出】

7
56

【提示】

所有答案小于?4611686018427387904

加强?10?组极限数据,未全部重测 by rvalue 2018.2.26

?

?

还是线段树而已

#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=100005;
#define ll long long
ll a[maxn];
int n,m;
struct SegmentTree{
    int l,r;
    long long dat;
    long long lazy_tag;
}t[maxn<<2];
void Pushdown(int p,int l,int r,int mid){
    t[p*2].dat+=t[p].lazy_tag*(mid-l+1);
    t[p*2+1].dat+=t[p].lazy_tag*(r-mid);
    t[p*2].lazy_tag+=t[p].lazy_tag;
    t[p*2+1].lazy_tag+=t[p].lazy_tag;
    t[p].lazy_tag=0;
}
void build(int p,int r){
    t[p].l=l;t[p].r=r;
    if(l==r){
        t[p].dat=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    t[p].dat=t[p*2].dat+t[p*2+1].dat;
}
ll Get(int p,int s,int tt){
    if(s>r||tt<l) return 0;
    if(s<=l&&r<=tt) return t[p].dat;
    int mid=(l+r)>>1;
    Pushdown(p,r,mid);
    return  Get(p*2,mid,s,tt)+ Get(p*2+1,tt);
}
void Add(int p,int tt,ll x){
    if(s>r||tt<l) return;
    if(s<=l&&r<=tt){
        t[p].dat+=x*(r-l+1);
        t[p].lazy_tag+=x;
        return;
    }
    int mid=(l+r)>>1;
    Pushdown(p,mid);
    Add(p*2,tt,x);Add(p*2+1,x);
    t[p].dat=t[p*2].dat+t[p*2+1].dat;
}
int main()
{
    freopen("shuliec.in","r",stdin);freopen("shuliec.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    scanf("%d",&m);
    build(1,1,n);
    for(int i=1;i<=m;i++){
        string s;cin>>s;
        if(s[0]==S){
            int l,r;scanf("%d%d",&l,&r);
            printf("%lldn",Get(1,n,r));    
        }
        else{
            int s,t;
            ll d;
            scanf("%d%d%lld",&s,&t,&d);
            Add(1,t,d);
        }
    }
    
    
    return 0;
 } 

?还有一个

标记永久化线段树

(编辑:李大同)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!

    推荐文章
      热点阅读