***第一次写的果断超时，所以百度了一下，知道我写的每一次都要递归最底层，这样会花费很多时间，第二次写得线段树的区间更新，因为一个条件写错了，真是让我坑到死，
这样区间相同的不必更新，省了很多时间。。。***
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <stack> #include <queue> using namespace std; typedef long long LL; #define oo 0x3f3f3f3f #define N 200100 struct node { int l, r; int s; } tree[N*4]; void build(int l, int r, int rt) { tree[rt].l=l; tree[rt].r=r; tree[rt].s=1; if(l==r) { return ; } int mid=(l+r)/2; build(l, mid, rt*2); build(mid+1, r, rt*2+1); } void update(int l, int r, int v, int rt) { if(tree[rt].s==v) return ; if(tree[rt].l==l&&tree[rt].r==r) { tree[rt].s=v; return ; } if(tree[rt].s!=-1) { tree[rt*2].s=tree[rt*2+1].s=tree[rt].s; tree[rt].s=-1; } int mid=(tree[rt].l+tree[rt].r)/2; if(r<=mid) update(l, r, v, rt*2); else if(l>mid) update(l, r, v, rt*2+1); else { update(l, mid, v, rt*2); update(mid+1, r, v, rt*2+1); } } int query(int rt) { if(tree[rt].s!=-1) return (tree[rt].r-tree[rt].l+1)*tree[rt].s; else return query(rt*2)+query(rt*2+1); } int main() { int T, n, m, a, b, c, cas=1; scanf("%d", &T); while(T--) { scanf("%d%d", &n, &m); build(1, n, 1); while(m--) { scanf("%d%d%d", &a, &b, &c); update(a, b, c, 1); } printf("Case %d: The total value of the hook is %d. ", cas++, query(1)); } return 0; } /* 20 3 2 1 2 2 2 2 3 */