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★★★?? 输入文件: 【题目描述】假设有一个长度为?n(n≤100000)?的数列?A,支持如下两种操作: 1. 将?Ai,Ai+1,…,Aj?的值均增加?d 2. 查询?As+As+1+?+At(s≤t)?的值。 根据操作要求进行正确操作并输出结果。 【输入格式】第一行为一个正整数?n,表示数列的大小。 第二行有?n?个整数,表示数列?A?各项的初始值。 第三行为一个整数?m?,表示操作的个数。 下面是?m?行,每行描述一个操作: ADD i j d(将?Ai,Ai+1,…,Aj(1≤i,j≤n)?的值均增加一个整数?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; } ?还有一个 标记永久化线段树 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |