这题是昨天的比赛题,昨天比赛完美被大一的虐了,感觉自己真是白活了,一头撞死算了,人家大一的做了5题,而我这个水货这做了两道签到题;明显昨天知道这个题目是线段树,刚开始还想用树状数组试试,后来写完了发现不是插线问点,结果可想而知,代码重写,再看时线段树,然后不会了,自己只会单点更新,以后努力了,没有时间给自己犹豫了;抓紧时间学习数据结构,还有贪心,图论,搜索,还有C++;任重道远;
其中本题的延迟标记完全不知道是什么原理;先把代码记着吧;今天这题调试了一天;各种跪,ORZ
#include <iostream> #include <cstdio> using namespace std; #define N 100005 #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1 | 1 __int64 sum[N<<2]; __int64 mark[N<<2]; inline void PushUp(int rt) { sum[rt]= sum[rt<<1] + sum[rt<<1|1]; } void PushDown(int rt,int len) { if(mark[rt]) { mark[rt<<1] += mark[rt]; mark[rt<<1|1] += mark[rt]; sum[rt<<1] += mark[rt] * (len-(len >> 1)); sum[rt<<1 | 1] += mark[rt] * (len >> 1); mark[rt]=0; } } void build(int l,int r,int rt) { mark[rt]=0; if(l == r) { scanf("%I64d",&sum[rt]); return; } int mid=(l+r)>>1; build(lson); build(rson); PushUp(rt); } void update(int L,int R,__int64 val,int l,int r,int rt) { if(L<=l&&R>=r) { mark[rt] += val; sum[rt] += val * (r-l+1); return ;//你妹啊没有加这个 return ;runtime error ORZ啊,今天早上开始就写这个东西,竟然是这样的问题[-_-] } PushDown(rt,r-l+1); int mid=(l+r)>>1; if(mid>=L) update(L,R,val,lson); if(mid<R)update(L,R,val,rson); PushUp(rt); } __int64 Query(int L,int R,int l,int r,int rt) { if(L<=l&&r<=R) return sum[rt]; PushDown(rt,r-l+1); int mid=(l+r)>>1; __int64 res=0; if(mid>=L) res += Query(L,R,lson); if(mid<R) res += Query(L,R,rson); return res; } int main() { int n,m,a,b; __int64 val; char op; scanf("%d%d",&n,&m); build(1,n,1); while(m--) { getchar(); scanf("%c %d%d",&op,&a,&b); if(op=='Q') { printf("%I64d\n",Query(a,b,1,n,1)); } else { scanf("%I64d",&val); update(a,b,val,1,n,1); } } return 0; }