题意:初始时整个区段值为1,然后每次使区段[L,R]内的值全部改为某个值,最后输出整个区段和
思路:线段树区间维护,成段替换。模板题,具体方法见代码,或者参看刘汝佳训练指南。
#include<cstdio> #include<cstring> #include<iostream> #define M ((R+L)>>1) #define ls (o<<1) #define rs (o<<1|1) #define lson ls,L,M #define rson rs,M+1,R #define MAXN 100005 using namespace std; int ql,qr; int v; int setv[MAXN*3]; int sumv[MAXN*3]; int T,n,Q,ca=0,_sum; void pushup(int o,int L,int R) { sumv[o]=0; if(setv[ls]>=0) sumv[o]+=setv[ls]*(M-L+1); else sumv[o]+=sumv[ls]; if(setv[rs]>=0) sumv[o]+=setv[rs]*(R-M); else sumv[o]+=sumv[rs]; //计算sumv的时候,如果儿子的set值大于等于0,则说明set值有效(因为初始化的时候set值都为-1) //set值有效时维护sumv要根据set值来维护。如果set值无效,则根据儿子的sumv维护即可 } void pushdown(int o){if(setv[o]>=0){setv[ls]=setv[rs]=setv[o];setv[o]=-1;}}//向下传递set标记 void build(int o,int L,int R) { if(L==R) {sumv[o]=1;return;}//初始时叶子结点为1 build(lson); build(rson); pushup(o,L,R); } void update(int o,int L,int R) { if(ql<=L && R<=qr){setv[o]=v;return;} pushdown(o);//向下传递set if(ql<=M) update(lson); if(M<qr) update(rson); pushup(o,L,R);//回收儿子标记 } void query(int o,int L,int R) { if(setv[o]>=0) {_sum+=setv[o]*(min(qr,R)-max(L,ql)+1);return;}//如果set值有效,则只需根据set值增加_sum if(ql<=L && R<=qr) {_sum+=sumv[o];return;} if(ql<=M) query(lson); if(qr>M) query(rson); } int main() { freopen("in.txt","r",stdin); scanf("%d",&T); while(T-- && scanf("%d%d",&n,&Q)) { memset(setv,-1,sizeof(setv)); build(1,1,n); while(Q--){scanf("%d%d%d",&ql,&qr,&v);update(1,1,n);} _sum=0,ql=1,qr=n; query(1,1,n); printf("Case %d: The total value of the hook is %d.\n",++ca,_sum); } return 0; }