一看便知道用线段树，题目比较水，一般简单的线段树就是两招 离散化和延迟标记
这道题目明显是用延迟标记，不要用链式树，用树状数组，否则会超空间。
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; int N,Q; typedef struct node { int l,r; int left_value,right_value; int delay; }node; node tree[100000*4+10]; int build(int p,int x,int y) { tree[p].delay=0; tree[p].l=x; tree[p].r=y; if(x==y) { tree[p].left_value=1; tree[p].right_value=0; } else { tree[p].left_value=build(p*2,x,(x+y)/2); tree[p].right_value=build(p*2+1,(x+y)/2+1,y); } return tree[p].left_value+tree[p].right_value; } int updates(int p,int x,int y,int v) { if(tree[p].delay!=0) { tree[p].left_value=((tree[p].l+tree[p].r)/2-tree[p].l+1)*tree[p].delay; tree[p].right_value=(tree[p].r-(tree[p].l+tree[p].r)/2)*tree[p].delay; if(tree[p].l!=tree[p].r) tree[p*2].delay=tree[p].delay; if(tree[p].l!=tree[p].r) tree[p*2+1].delay=tree[p].delay; tree[p].delay=0; } if(!(x<=tree[p].r&&y>=tree[p].l)) return tree[p].left_value+tree[p].right_value; if(x<=tree[p].l&&y>=tree[p].r) { tree[p].left_value=((tree[p].l+tree[p].r)/2-tree[p].l+1)*v; tree[p].right_value=(tree[p].r-(tree[p].l+tree[p].r)/2)*v; if(tree[p].l!=tree[p].r) tree[p*2].delay=v; if(tree[p].l!=tree[p].r) tree[p*2+1].delay=v; } else { tree[p].left_value=updates(p*2,x,y,v); tree[p].right_value=updates(p*2+1,x,y,v); } return tree[p].left_value+tree[p].right_value; } int main() { int T; scanf("%d",&T); for(int Case=1;Case<=T;Case++) { scanf("%d%d",&N,&Q); build(1,1,N); for(int i=1;i<=Q;i++) { int a,b,v; scanf("%d%d%d",&a,&b,&v); updates(1,a,b,v); } printf("Case %d: The total value of the hook is %d.\n", Case,tree[1].left_value+tree[1].right_value); } }