Just a Hook
题意:给定一个长度为N(1<=N<=100,000)初始为1的序列；之后有Q次区间修改(0<=Q<=100,000)，即将区间的值全部改成v(1<= v <= 3);问最后所有值的和为多少？
线段树区间：先要对线段树的rt与l,r之间的关系清楚，才能很容易的编写出延迟标记的线段树区间修改代码；
rt与l,r之间的关系:线段树的树根rt总是1，每次传l,r,rt都表示rt这个节点覆盖的实际区间范围为[l,r];但是有时需要输入初始化时，我们知道是在bulid()的 l == r时赋给a[rt]的；这就是原始数组的下标和在线段树中的下标的不同含义(我们一般不管在原始下标线段树中的下标是多少，而只看根节点的覆盖区间，这样二分下去到了相等得到的就是实际数组中的下标，同时这也是为什么一般线段树的数组要开到最大点数的四倍的原因)；
延迟标记 : 其实想想就可以实现代码了，就是增加一个标记数组id[]；初始化为-1；在每一次区间修改时，不是直接朴素地对每一个原始的值改变(即当l == r时改变)，而是对一个区间的根节点改变，这样就标记为这个区间的改变；只是当要改变的区间需要二分时，就需要判断当前的rt节点是否已经被标记了，如果被标记了，就需要将标记pushdown到子节点(现在孩子节点出现了不同的值，父节点不能代表下面所有孩子节点的值了)；就是这样~~
ps:904MS 还是慢了很多。。
#include<iostream> #include<cstdio> #include<cstring> #include<string.h> #include<algorithm> #include<map> #include<queue> #include<vector> #include<cmath> #include<stdlib.h> #include<time.h> #include<stack> #include<set> using namespace std; #define rep0(i,l,r) for(int i = (l);i < (r);i++) #define rep1(i,l,r) for(int i = (l);i <= (r);i++) #define rep_0(i,r,l) for(int i = (r);i > (l);i--) #define rep_1(i,r,l) for(int i = (r);i >= (l);i--) #define MS0(a) memset(a,0,sizeof(a)) #define MS1(a) memset(a,-1,sizeof(a)) #define inf 0x3f3f3f3f #define lson l, m, rt << 1 #define rson m+1, r, rt << 1|1 typedef __int64 ll; template<typename T> void read1(T &m) { T x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} m = x*f; } template<typename T> void read2(T &a,T &b){read1(a);read1(b);} template<typename T> void read3(T &a,T &b,T &c){read1(a);read1(b);read1(c);} template<typename T> void out(T a) { if(a>9) out(a/10); putchar(a%10+'0'); } const int MAXN = 100100; int id[MAXN<<2],a[MAXN<<2]; void build(int l,int r,int rt) { id[rt] = -1;//标记是要标记到每一个结点; if(l == r){ a[rt] = 1; return ; } int m = l+r>>1; build(lson); build(rson); //upshup(rt); } void pushdown(int rt) { id[rt<<1] = id[rt<<1|1] = id[rt]; id[rt] = -1; } void update(int L,int R,int v,int l,int r,int rt) { if(L <= l && r <= R){ id[rt] = v; //cout<<l<<" lr "<<r<<endl; return ; } int m = l+r>>1; if(~id[rt]) pushdown(rt); if(L <= m) update(L,R,v,lson); if(R > m) update(L,R,v,rson); } int query(int l,int r,int rt) { if(id[rt] != -1) return id[rt]*(r-l+1); if(l == r) return a[rt]; int m = l+r>>1,ret = 0; ret += query(lson); ret += query(rson); return ret; } int main() { int n,T,kase = 1; read1(T); while(T--){ read1(n); build(1,n,1); int Q,l,r,v; read1(Q); while(Q--){ read3(l,r,v); update(l,r,v,1,n,1); } printf("Case %d: The total value of the hook is %d. ",kase++,query(1,n,1)); } return 0; }