sdut 2880 Devour Magic 线段树 区间更新和区间替换

新和区间替换"/>

sdut 2880 Devour Magic 线段树 区间更新和区间替换

题意：

给你一个1~n的区间，每过一个单位时间区间值加一

现在有一个操作 t l r 表示在t时间把 l--->r的值累加为ans然后清零

分析：

就是成段更新和成段替换 替换的优先级高于成段替换

ACcode：

#include <cstdio>
#include <cstring>
#define ll long long
using namespace std;
#define maxn 100010
#define m ((l+r)>>1)
#define tmp (st<<1)
#define lson l,m,tmp
#define rson m+1,r,tmp|1
#define push_up(x) sum[x]=sum[x<<1]+sum[x<<1|1]
int sum[maxn<<2],add[maxn<<2];
bool col[maxn<<2];
inline void Scan(int &x) {char c;while((c=getchar())<'0' || c>'9');x=c-'0';while((c=getchar())>='0' && c<='9') x=(x<<3)+(x<<1)+c-'0';
}
inline void ppush_down(int st){if(!col[st]){add[tmp]=add[tmp|1]=col[tmp]=col[tmp|1]=col[st];sum[tmp]=sum[tmp|1]=0;col[st]=1;}
}
inline void push_down(int st,int len){if(add[st]){add[tmp]+=add[st];add[tmp|1]+=add[st];sum[tmp]+=add[st]*(len-(len>>1));sum[tmp|1]+=add[st]*(len>>1);add[st]=0;}
}
inline void update(int L,int R,int c,int l,int r,int st){if(L<=l&&r<=R){add[st]+=c;sum[st]+=c*(r-l+1);return;}push_down(st,r-l+1);if(L<=m)update(L,R,c,lson);if(R>m)update(L,R,c,rson);push_up(st);
}
inline void update2(int L,int R,int l,int r,int st){if(L<=l&&r<=R){col[st]=add[st]=sum[st]=0;return;}ppush_down(st);if(L<=m)update2(L,R,lson);if(m<R)update2(L,R,rson);push_up(st);
}
inline ll qurey(int L,int R,int l,int r,int st){if(L<=l&&r<=R)return sum[st];ppush_down(st);push_down(st,r-l+1);ll ret=0;if(L<=m)ret+=qurey(L,R,lson);if(R>m)ret+=qurey(L,R,rson);return ret;
}
int main(){int n,loop,q;Scan(loop);while(loop--){memset(sum,0,sizeof(sum));memset(add,0,sizeof(add));memset(col,true,sizeof(col));Scan(n);Scan(q);int temp=0;ll ans=0;for(int i=0;i<q;++i){int t,l,r;Scan(t);Scan(l);Scan(r);update(1,n,(ll)t-temp,1,n,1);ans+=qurey(l,r,1,n,1);update2(l,r,1,n,1);temp=t;}printf("%lld\n",ans);}return 0;
}
/*
44
10 5
1 1 10
2 3 10
3 5 10
4 7 10
5 9 10
10 4
1 1 10
2 3 10
3 5 10
4 7 10
10 3
1 1 10
2 3 10
4 7 10
10 1
1 1 10
10 1
8 1 10
*/
*/