第五届山东省ACM Devour Magic

山东省ACM Devour Magic"/>

第五届山东省ACM Devour Magic

Devour Magic

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

就是在原来的基础上增加了清零的操作，不过这个清零（实际代码中也可以置为任意值）的操作通过flag标志和一个sset变量来保存下要置的数，其他操作和正常pushdown一样，每次在输入时记录上一次更新的时间last，这一次直接t-last就好了。。。

之前的一个超时代码也先粘在这里吧，（标记的可能多搜了！！！），但是提交AC的代码和自己的思路是一模一样的，具体现在也不知道问题出在哪里

超时代码：

///线段树区间更新  
#include<algorithm>  
#include<cstdio>  
#include<cstring>  
#include<cstdlib>  
#include<iostream>  
#include<vector>  
#include<queue>  
#include<stack>  
#include<iomanip>  
#include<string>  
#include<climits>  
#include<cmath>  
#define INF 0x3f3f3f3f  
#define MAX 1100000  
#define LL long long  
using namespace std;  
LL n,m;  
LL coun=0;  
int xx;  struct Tree  
{  LL l,r;  LL sum,add;  
};  
Tree tree[MAX*8];  void pushup(LL x)  ///更新父节点  
{  tree[x].sum=tree[ x<<1 ].sum+tree[ (x<<1)+1 ].sum;  
}  void pushdown(LL x)  ///用于更新add数组  
{  if(x>xx){  tree[x].sum = 0;  return ;  }  LL tmp = x<<1 ;  if(tree[x].add == -INF){  //  cout<<x<<"----------------------"<<endl;  tree[tmp].add = -INF ;  ///由子节点通过增加  tree[tmp+1].add = -INF;  tree[tmp].sum = 0;  tree[tmp+1].sum = 0;  tree[x].add=0;  tree[x].sum=0;  return ;  }  if( tmp > xx ) return ;  if(tree[tmp].add == -INF )   pushdown(tmp);  if(tree[tmp+1].add == -INF)  pushdown(tmp+1);  tree[tmp].add +=  tree[x].add;  ///由子节点通过增加  tree[tmp].sum += tree[x].add*(tree[tmp].r-tree[tmp].l+1);  tree[tmp+1].add += tree[x].add;  tree[tmp+1].sum += tree[x].add*(tree[tmp+1].r-tree[tmp+1].l+1);  if(tmp>xx) cout<<tmp<<"  "<<tree[tmp].add<<"  "<<tree[tmp].add<<"  "<<tree[tmp].l<<"  "<<tree[tmp].r<<endl;  tree[x].add=0;  
}  void build(int l,int r,int x)  
{  tree[x].l=l , tree[x].r=r , tree[x].add=0;  if(l==r)  {  tree[x].sum = 0;  ///子节点初始化  tree[x].add = 0;  return ;  }  int tmp=x<<1;  int mid=(l+r)>>1;  build(l,mid,tmp);  build(mid+1,r,tmp+1);  pushup(x);  ///建立时需根据子节点更细父亲节点  
}  void update(LL l,LL r,LL c,LL x)  ///分别表示区间的左 ， 右 ， 增加的值  ，当前父亲节点  
{  if(r<tree[x].l||l>tree[x].r||x>xx)   return ;  if(l<=tree[x].l&&r>=tree[x].r)  ///该区间为需要更新区间的子区间  {  // cout<<"************\n";  if(c==-INF){  tree[x].add = -INF;  tree[x].sum = 0;  return ;  }  if(x>xx)  return ;  if(tree[x].add == -INF ) pushdown(x);  tree[x].add += c ;  tree[x].sum += c*(tree[x].r-tree[x].l+1); ///区间长度*要增加的数值  return ;  }  ///如果比当前的范围还小，就通过该节点向下更新下面的节点  if(tree[x].add  )  pushdown(x);  ///更新从上向下更新add  LL tmp=x<<1;  if(tmp>xx){  pushup(x);  return ;  }  update(l,r,c,tmp);  update(l,r,c,tmp+1);  
}  LL query(LL l,LL r,LL x)  
{  ///if(r<tree[x].l||l>tree[x].r)     return -INF;//要更新的区间不在该区间上（输入有误）  if(l<=tree[x].l&&r>=tree[x].r)    ///要计算的区间包括了该区间  {  return tree[x].sum;  }  if( tree[x].add&&tree[x].add!=-INF )   pushdown(x);  ///如果add不为零，对查询可能用到的add更新  LL tmp=x<<1;  if(tmp>xx) return 0;  LL mid=(tree[x].l+tree[x].r)>>1;  if(r<=mid)   return query(l,r,tmp);  else if(l>mid)  return query(l,r,tmp+1);  else  return query(l,mid,tmp)+query(mid+1,r,tmp+1);  
}  int main()  
{  int xxx;  scanf("%d",&xxx);  while(xxx--)  {  scanf("%I64d%I64d",&n,&m);  xx=4*n;  coun=0;  build(1,n,1);  LL last=0;  while(m--)  {  LL l,r,time;  scanf("%I64d%I64d%I64d",&time,&l,&r);  update(1,n,time-last,1);  
/* cout<<"加"<<time-last<<endl; for(int i=1;i<=60;i++) cout<<i<<":"<<tree[i].add<<' '<<tree[i].sum<<"    "; cout<<endl;*/  last = time ;  coun+=query(l,r,1);  update(l,r,-INF,1);  
/* for(int i=1;i<=60;i++) cout<<i<<":"<<tree[i].add<<' '<<tree[i].sum<<"      "; cout<<endl;*/  }  printf("%I64d\n",coun);  }  return 0;  
}  
/************************************** Problem id  : SDUT OJ 2880  User name   : 张士卫  Result      : Time Limit Exceeded  Take Memory : 0K  Take Time   : 2010MS  Submit Time : 2016-04-02 09:36:52   
**************************************/  

AC代码：

#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 add;///区间增加值  int sset;    ///区间里的数设为v  bool flag;///标记是否设置为v  int mid(){  return ((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){  int L=L(root),R=R(root);  if(tree[root].flag){  tree[L].add=tree[R].add=0;  tree[L].sset=tree[R].sset=tree[root].sset;  tree[L].flag=tree[R].flag=true;  tree[L].sum=tree[root].sset*(tree[L].right-tree[L].left+1);  tree[R].sum=tree[root].sset*(tree[R].right-tree[R].left+1);  tree[root].flag=false;  }  if(tree[root].add){  ///正常pushdown  tree[L].add+=tree[root].add;  tree[R].add+=tree[root].add;  tree[L].sum+=tree[root].add*(tree[L].right-tree[L].left+1);  tree[R].sum+=tree[root].add*(tree[R].right-tree[R].left+1);  tree[root].add=0;  }  
}  void build(int root,int left,int right){  tree[root].left=left;  tree[root].right=right;  tree[root].add=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].add+=add;  tree[root].sum+=add*(right-left+1);  return;  }  pushDown(root);  int mid=tree[root].mid(),L=L(root),R = R(root);  if(right<=mid)     update(L,left,right,add);  else if(left>mid)  update(R,left,right,add);  else{  update(L,left,mid,add);  update(R,mid+1,right,add);  }  pushUp(root);  
}  void setf(int root,int left,int right,int sset){  if(tree[root].left==left&&tree[root].right==right){  tree[root].add=0;  tree[root].sum=sset*(right-left+1);  tree[root].sset=sset;  tree[root].flag=true;  return;  }  pushDown(root);  int mid=tree[root].mid(),L=L(root),R = R(root);  if(right<=mid)     setf(L,left,right,sset);  else if(left>mid)  setf(R,left,right,sset);  else{  setf(L,left,mid,sset);  setf(R,mid+1,right,sset);  }  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区间设为0  lastTime=t;  }  printf("%lld\n",sum);  }  return 0;  
}