分析： 只查询一次（总和）。toadd 表示以下全部替换为此值（而不是累加）。初始每个结点为1。
类型：成段更新（lazy标记）。线段树......（ps. 据说树状数组能做成段的？怎么做？再说~...
代码：
//颜色：1 2 3//You may consider the original hook is made up of cupreous sticks.#include#include #include using namespace std;#define lc e<<1#define rc e<<1|1#define MAXN 100000struct node{ int l, r, mid, v, toadd; } a[MAXN*4]; //toadd表示颜色值{0/1/2/3}int n;void pushup(int e) { a[e].v=a[lc].v+a[rc].v; }void pushdown(int e) { int t = a[e].toadd; if(t) { a[e].toadd = 0; a[lc].v=(a[lc].r-a[lc].l+1)*t; a[rc].v=(a[rc].r-a[rc].l+1)*t; a[lc].toadd=a[rc].toadd=t; }}void build(int l, int r, int e) //(1, n, 1){ a[e].l=l; a[e].r=r; if(l==r) a[e].v=1; else { a[e].mid=(l+r)>>1; build(l, a[e].mid, lc); build(a[e].mid+1, r, rc); pushup(e); }}void update(int L, int R, int c, int l, int r, int e){ if(L<=l && r<=R) { a[e].v = (a[e].r-a[e].l+1)*c; a[e].toadd = c;//printf("L:%d R:%d l:%d r:%d c:%d a[e].v=%d\n", L, R, l, r, c, a[e].v); } else // l L R r { pushdown(e); //这里不推下去怎么对！！！2~ if(L<=a[e].mid) update(L, R, c, l, a[e].mid, lc); if(a[e].mid