SDUTOJ2880 Devour Magic（线段树两重延迟标记）

线段树两重延迟标记）"/>

SDUTOJ2880 Devour Magic（线段树两重延迟标记）

题意：

每个点能量每秒加1

按时间顺序给你N组时间+区间

表示在时间t时取走区间内的能量

问取走了多少能量

思路：

区间修改区间查询

加能量数延迟一下

去走后延迟一下

用两个flag保存延迟状态

/* ***********************************************
Author        :devil
Created Time  :2016/5/14 17:23:34
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <stdlib.h>
using namespace std;
const int N=1e5+7;
long long tree[N<<2];
bool flag[N<<2],flag2[N<<2];
int done[N<<2];
void pushdown2(int node,int l,int r)
{flag2[node]=0;flag[node]=0;tree[node]=0;done[node]=0;if(l==r) return ;int m=(l+r)>>1;tree[node<<1]=0;flag2[node<<1]=1;tree[node<<1|1]=0;flag2[node<<1|1]=1;
}
void pushdown(int node,int l,int r)
{if(flag2[node]) pushdown2(node,l,r);flag[node]=0;if(l==r) return ;int m=(l+r)>>1;if(flag2[node<<1]) pushdown2(node<<1,l,m);tree[node<<1]+=(m-l+1)*done[node];flag[node<<1]=1;done[node<<1]+=done[node];if(flag2[node<<1|1]) pushdown2(node<<1|1,m+1,r);tree[node<<1|1]+=(r-m)*done[node];flag[node<<1|1]=1;done[node<<1|1]+=done[node];//printf("%d %d %d %d %d\n",l,r,tree[node<<1],tree[node<<1|1],done[node]);done[node]=0;
}
void update(int node,int l,int r,int add)
{if(flag2[node]) pushdown2(node,l,r);flag[node]=1;done[node]+=add;tree[node]+=(r-l+1)*add;
}
long long query(int node,int l,int r,int x,int y)
{if(l>=x&&r<=y){flag2[node]=1;long long tmp=tree[node];tree[node]=0;//printf("%d %d %d\n",l,r,tree[node]);return tmp;}if(flag2[node]) pushdown2(node,l,r);if(flag[node]) pushdown(node,l,r);int m=(l+r)>>1,ans=0;if(x<=m) ans+=query(node<<1,l,m,x,y);if(y>m) ans+=query(node<<1|1,m+1,r,x,y);tree[node]=tree[node<<1]+tree[node<<1|1];return ans;
}
int main()
{//freopen("in.txt","r",stdin);int t;scanf("%d",&t);while(t--){int n,m,s,x,y,now=0;long long ans=0;scanf("%d%d",&n,&m);memset(tree,0,sizeof(tree));memset(done,0,sizeof(done));memset(flag,0,sizeof(flag));memset(flag2,0,sizeof(flag2));while(m--){scanf("%d%d%d",&s,&x,&y);update(1,1,n,s-now);now=s;ans+=query(1,1,n,x,y);}printf("%lld\n",ans);}return 0;
}

转载于:.html