2014山东省第五届ACM省赛 Devour Magic

山东省第五届ACM省赛 Devour Magic"/>

2014山东省第五届ACM省赛 Devour Magic

题意：n个单位，每个单位每秒增加1法力，在某些时间取走一些区间的法力值（取走之后该区间所有单位的法力变为0），求取得的所有法力值。

思路：线段树区间更新，求和。区间求和之后要把该区间清零。set+add操作，set在先，add在后。

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;#define L(root) ((root)<<1)
#define R(root) (((root)<<1)|1)const int MAXN=1e5+10;//
int numbers[MAXN];//初始值struct node
{int left,right;long long sum;int delta;//延迟更新标志int v;//用于清零bool flag;//标记是否设置为v，用于清零int mid(){return left+((right-left)>>1);}
} tree[MAXN*4]; //4倍空间void pushUp(int root)
{tree[root].sum=tree[L(root)].sum+tree[R(root)].sum;
}void pushDown(int root)
{if(tree[root].flag){tree[L(root)].delta=tree[R(root)].delta=0;tree[L(root)].v=tree[R(root)].v=tree[root].v;tree[L(root)].flag=tree[R(root)].flag=true;tree[L(root)].sum=tree[root].v*(tree[L(root)].right-tree[L(root)].left+1);tree[R(root)].sum=tree[root].v*(tree[R(root)].right-tree[R(root)].left+1);tree[root].flag=false;}if(tree[root].delta)//延迟更新标志{tree[L(root)].delta+=tree[root].delta;tree[R(root)].delta+=tree[root].delta;tree[L(root)].sum+=tree[root].delta*(tree[L(root)].right-tree[L(root)].left+1);tree[R(root)].sum+=tree[root].delta*(tree[R(root)].right-tree[R(root)].left+1);tree[root].delta=0;}
}void build(int root,int left,int right)
{tree[root].left=left;tree[root].right=right;tree[root].delta=0;tree[root].flag=false;if(left==right){tree[root].sum=numbers[left];return;}int mid=tree[root].mid();build(L(root),left,mid);build(R(root),mid+1,right);pushUp(root);
}long long query(int root,int left,int right)
{if(tree[root].left==left&&tree[root].right==right){return tree[root].sum;}pushDown(root);int mid=tree[root].mid();if(right<=mid){return query(L(root),left,right);}else if(left>mid){return query(R(root),left,right);}else{return query(L(root),left,mid)+query(R(root),mid+1,right);}
}void update(int root,int left,int right,int add)
{if(tree[root].left==left&&tree[root].right==right){tree[root].delta+=add;tree[root].sum+=add*(right-left+1);return;}pushDown(root);int mid=tree[root].mid();if(right<=mid){update(L(root),left,right,add);}else if(left>mid){update(R(root),left,right,add);}else{update(L(root),left,mid,add);update(R(root),mid+1,right,add);}pushUp(root);
}void setf(int root,int left,int right,int v)
{if(tree[root].left==left&&tree[root].right==right){tree[root].delta=0;tree[root].sum=v*(right-left+1);tree[root].v=v;tree[root].flag=true;return;}pushDown(root);int mid=tree[root].mid();if(right<=mid){setf(L(root),left,right,v);}else if(left>mid){setf(R(root),left,right,v);}else{setf(L(root),left,mid,v);setf(R(root),mid+1,right,v);}pushUp(root);
}int main()
{memset(numbers,0,sizeof(numbers));int T;int n,m;int t,l,r;int i;int lastTime;long long sum;scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);build(1,1,n);lastTime=0;sum=0;for(i=0; i<m; ++i){scanf("%d%d%d",&t,&l,&r);update(1,1,n,t-lastTime);sum+=query(1,l,r);setf(1,l,r,0);//l到r区间设为0lastTime=t;}printf("%lld\n",sum);}return 0;
}