sdut 2880 Devour Magic

sdut 2880 Devour Magic"/>

sdut 2880 Devour Magic

打错一个变量，调了一个晚上。。。。给跪了。

题目大意：一条线上有n个单元，每个单元含有一定数量的mana，初始值为0，每经过一个时刻，每个单元的mana会增加1。

现有m次操作（按时间顺序给出），每次给出t,l,r，表示在t时刻取走区间[l,r]内的所有mana。

问最终能获得多少mana。

分析：典型的成段更新，区间查询问题。

使用线段树维护区间和。更新时，使用两个标记，一个add记录增量，一个lazy记录是否清零。

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long LL;
#define N 100000
#define lson l,m,rt<<1
#define rson m+1,r,(rt<<1)|1
LL s[N<<2],add[N<<2],lazy[N<<2];
inline void PushUp(int rt){s[rt]=s[rt<<1]+s[(rt<<1)|1];
}
inline void PushDown(int rt,int m)
{if(lazy[rt]){lazy[rt<<1]=lazy[(rt<<1)|1]=lazy[rt];lazy[rt]=add[rt<<1]=add[(rt<<1)|1]=s[rt<<1]=s[(rt<<1)|1]=lazy[rt]=0;}if(add[rt]){add[rt<<1]+=add[rt];add[(rt<<1)|1]+=add[rt];s[rt<<1]+=add[rt]*(m-(m>>1));s[(rt<<1)|1]+=add[rt]*(m>>1);add[rt]=0;}
}
void update(int L,int R,int c,int l,int r,int rt)
{if(L<=l&&r<=R){if(c){add[rt]+=c;s[rt]+=(LL)c*(r-l+1);}else{add[rt]=s[rt]=0;lazy[rt]=1;}return;}PushDown(rt,r-l+1);int m=(l+r)>>1;if(L<=m) update(L,R,c,lson);if(m<R) update(L,R,c,rson);PushUp(rt);
}LL query(int L,int R,int l,int r,int rt)
{if(L<=l&&r<=R) return s[rt];PushDown(rt,r-l+1);int m=(l+r)>>1;LL ret=0;if(L<=m) ret+=query(L,R,lson);if(m<R) ret+=query(L,R,rson);return ret;
}int main()
{int n,t,T,L,R,m;scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);memset(s,0,sizeof(s));memset(lazy,0,sizeof(lazy));memset(add,0,sizeof(add));LL ans=0;int pre=0;while(m--){scanf("%d%d%d",&T,&L,&R);update(1,n,T-pre,1,n,1);ans+=query(L,R,1,n,1);update(L,R,0,1,n,1);pre=T;}printf("%lld\n",ans);}return 0;
}