题目大意
给定一个长度为n的序列A,每个元素值初始全部为1,接下来有m个操作,每次给定操作区间[X,Y]和一个值v,表示把AX,AX+1,…AY的值全部修改为v,完成m次在操作之后要求你求出序列的总和
题解
区间修改的模板题。。。需要用到懒惰标记(搞了好久才弄懂o(╯□╰)o)。。。
代码:
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define MAXN 100005 #define lson l, m , s << 1 #define rson m + 1 , r , s << 1 | 1 using namespace std; int sumv[MAXN<<2],setv[MAXN<<2]; void PushUp(int s) { sumv[s]=sumv[s<<1]+sumv[s<<1|1]; } void PushDown(int s,int m) { if(setv[s]) { setv[s<<1]=setv[s<<1|1]=setv[s]; sumv[s<<1]=(m-(m>>1))*setv[s]; sumv[s<<1|1]=(m>>1)*setv[s]; setv[s]=0; } } void build(int l,int r,int s) { sumv[s]=1; setv[s]=0; if(l==r) return; int m=(l+r)>>1; build(lson); build(rson); PushUp(s); } void update(int ql,int qr,int d,int l,int r,int s) { if(ql<=l&&r<=qr) { setv[s]=d; sumv[s]=d*(r-l+1); return; } PushDown(s,r-l+1); int m=(l+r)>>1; if(ql<=m) update(ql,qr,d,lson); if(qr>m) update(ql,qr,d,rson); PushUp(s); } int main(void) { int n,m,T,x,y,p=0,z; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); build(1,n,1); while(m--) { scanf("%d%d%d",&x,&y,&z); update(x,y,z,1,n,1); } printf("Case %d: The total value of the hook is %d.\n",++p,sumv[1]); } return 0; }