首页 > 代码库 > PKU 3468 A Simple Problem with Integers
PKU 3468 A Simple Problem with Integers
题目大意:
有N,M两个数
Q 表示查询, 后面两个数a b,表示查询从a 到b计算它们的和
C 表示增加 后面三个数a,b,c 表示从a开始,一直到b,每个数都增加c
有N,M两个数
Q 表示查询, 后面两个数a b,表示查询从a 到b计算它们的和
C 表示增加 后面三个数a,b,c 表示从a开始,一直到b,每个数都增加c
除了查询要进行输出,增加不要输出
#include<iostream> using namespace std; #define LL(x)((x)<<1) #define RR(x)((x)<<1|1) struct_Seg_Tree{ int left,right; long long sum; int add; int calmid(){ return (left+right)/2; } int caldis(){ return right-left+1; } }tt[1000000]; int val[1000002]; long long build(int l,int r,int idx){ tt[idx].left=l; tt[idx].right=r; tt[idx].add=0; if(l==r){ return tt[idx].sum=val[l]; } return tt[idx].sum=build(l,mid,LL(idx)+build(mid+1,r,RR(idx))); } void update(int l,int r,int add,int idx){ if(l<=tt[idx].left&&r>=tt[idx].right){ tt[idx].add+=add; tt[idx].sum+=(long long)tt[idx].caldis()*add;//通过乘以后来添加的数 return ; } if(tt[idx].add){ tt[LL(idx).sum]+=(long long)tt[LL(idx)].caldis()*tt[idx].add; tt[RR(idx).sum]++(long long)tt[RR(idx)].caldis()*tt[idx].add; tt[LL(idx)].add+=tt[idx].add; tt[RR(idx)].add+=tt[idx].add; tt[idx].add=0; } int mid=tt[idx].calmid(); if(l<=mid) update(l,r,add,LL(idx)); if(mid<r) update(l,r,add,RR(idx)); tt[idx].sum = tt[LL(idx)].sum + tt[RR(idx)].sum; } long long query(int l,int r,int idx){ if(l==tt[idx].left&&r==tt[idx].right){ return tt[idx].sum; } if(tt[idx].add){ tt[LL(idx)].sum += (long long )tt[LL(idx)].caldis() * tt[idx].add; tt[RR(idx)].sum += (long long)tt[RR(idx)].caldis() * tt[idx].add; tt[LL(idx)].add += tt[idx].add; tt[RR(idx)].add += tt[idx].add; tt[idx].add = 0; } int mid=tt[idx].calmid(); if(r<=mid){ return query(l,r,LL(idx)); } else if(mid<1){ return query(l,r,RR(idx)); } else{ return query(l,mid,LL(idx)+query(mid+1,r,RR(idx)); } } int main(){ int n,m; while(scanf("%d %d",&n,&m)==2){ for(int i=1;i<=n;i++) scanf("%d",&val[i]); build(1,n,1); while(m--){ char com[2]; scanf("%s",com); if(com[0]=='Q'){ int a,b; scanf("%d %d",&a,&b); pirntf("lld\n",query(a,b,1)); }else{ int a,b,c; scanf("%d %d %d",&a,&b,&c); update(a,b,c,1); } } } }
PKU 3468 A Simple Problem with Integers
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。