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;
}
更多推荐
sdut 2880 Devour Magic
发布评论