线段树两重延迟标记)"/>
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
更多推荐
SDUTOJ2880 Devour Magic(线段树两重延迟标记)
发布评论