HDU 1698 Just a Hook 线段树 区间更新 惰性标记

#include<stdio.h> #include<string> #include<cstring> #include<queue> #include<algorithm> #include<functional> #include<vector> #include<iomanip> #include<math.h> #include<iostream> #include<sstream> #include<set> #include<climits> #include<map> #include<bitset> using namespace std; const int MAX=100005; int F[4*MAX],Mark[4*MAX]= {0}; void build(int x,int left,int right) { if (left==right) { F[x]=1; return; } int mid=(left+right)/2; build(x*2,left,mid); build(x*2+1,mid+1,right); F[x]=F[x*2]+F[x*2+1]; } void change(int x,int left,int right,int L,int R,int num) { if (left>R||right<L) return; if (left>=L&&right<=R) { F[x]=(right-left+1)*num; Mark[x]=num; return; } int mid=(left+right)/2; if (Mark[x]) { Mark[x*2]=Mark[x*2+1]=Mark[x]; F[x*2]=(mid-left+1)*Mark[x]; F[x*2+1]=(right-mid)*Mark[x]; Mark[x]=0; } if (L<=mid) change(x*2,left,mid,L,R,num); if (R>mid) change(x*2+1,mid+1,right,L,R,num); F[x]=F[x*2]+F[x*2+1]; } int main() { int T,N,Q,a,b,z; scanf("%d",&T); for (int cases=1;cases<=T;cases++) { memset(Mark,0,sizeof(Mark)); scanf("%d%d",&N,&Q); build(1,1,N); for (int j=1;j<=Q;j++) { scanf("%d%d%d",&a,&b,&z); change(1,1,N,a,b,z); } printf("Case %d: The total value of the hook is %d.\n",cases,F[1]); } return 0; }