一個有初值的數列、區間加、區間查

用線段樹直接水過

然而并沒有1A，主要是做題太快沒看規模結果沒注意線段樹要用longlong建

臥槽怎么可以這么坑爹，害得我看見wa心慌了，還以為連線段樹都要跪

一開始在寫下傳（MDZZ）然后發現沒什么操作就刪了

1 #include <cstdio> 2 #include <iostream> 3 #define mid (l+r)/2 4 long long t[400001],tr[400001]; 5 int n,m; 6 void add(int now,int l,int r,int x,int y) 7 { 8 t[now]+=y; 9 if(l==r) 10 return; 11 if(x<=mid) 12 add(now*2,l,mid,x,y); 13 else 14 add(now*2+1,mid+1,r,x,y); 15 } 16 void plus(int now,int l,int r,int x,int y,int z) 17 { 18 if(l==x && r==y) 19 { 20 tr[now]+=z; 21 return; 22 } 23 if(x<=mid) 24 plus(now*2,l,mid,x,std::min(y,mid),z); 25 if(y>mid) 26 plus(now*2+1,mid+1,r,std::max(x,mid+1),y,z); 27 t[now]=t[now*2]+tr[now*2]*(mid-l+1)+t[now*2+1]+tr[now*2+1]*(r-mid); 28 } 29 long long que(int now,int l,int r,int x,int y) 30 { 31 if(l==x && r==y) 32 return t[now]+tr[now]*(r-l+1); 33 long long sum=(y-x+1)*tr[now]; 34 if(x<=mid) 35 sum+=que(now*2,l,mid,x,std::min(y,mid)); 36 if(y>mid) 37 sum+=que(now*2+1,mid+1,r,std::max(x,mid+1),y); 38 return sum; 39 } 40 int main() 41 { 42 scanf("%d%d",&n,&m); 43 for(int i=1;i<=n;i++) 44 { 45 int x; 46 scanf("%d",&x); 47 add(1,1,n,i,x); 48 } 49 for(int i=1;i<=m;i++) 50 { 51 char ch=getchar(); 52 for(;ch!='C' && ch!='Q';ch=getchar()); 53 if(ch=='C') 54 { 55 int x,y,z; 56 scanf("%d%d%d",&x,&y,&z); 57 plus(1,1,n,x,y,z); 58 } 59 else 60 { 61 int x,y; 62 scanf("%d%d",&x,&y); 63 printf("%lld\n",que(1,1,n,x,y)); 64 } 65 } 66 return 0; 67 }

?

轉載于:https://www.cnblogs.com/wanglichao/p/5684426.html

總結

以上是生活随笔為你收集整理的bzoj3212 pku3468 A Simple Problem with Integers的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。