//==========================
蒟蒻Macaulish： 转载要声明！
//==========================
好久没写题解了。
但是这题太神了然后做法太神了于是写一下。
这题做法很多，比如黄学长hzw的权值线段树套线段树，比如学长云的bit套主席树（其实是写法更神然后我不会用）。
然后看到hzhwcmhf大神题解。
http://tieba.baidu.com/p/2246783535
震惊了。
好了开说说做法。建一颗朴素的线段树，树的每个点表示每个区间，然后每个区间建两棵树，一棵是mark树，一棵是all树，两棵都是权值线段树。
“mark表示该区间每个点上都会加上mark线段树里的元素
all表示该区间所有点的元素集合”这道题麻烦的地方就在与标记，如果标记要下传的话，那么每次可能要下传很多个点。
于是标记永久化，就是不要下传。
对于修改：如果修改区间是当前点区间，那么就加入mark中。如果不是，那么就加入all。操作都是单点修改。加入mark时为c+1，加入all是为c+len
对于询问：首先包含在查询区间内的区间的所有的all，然后mark要去掉没有重合在一起的地方，乘回差值。
（太久没写题解都不知道怎么说了）
速度还是挺快的
type arr=record all,mark:longint; end;const maxn=10000000;var tree:array[0..maxn]of arr; size,lson,rson,root1,root2:array[0..maxn]of longint; tot,sum,n,m,i,j,k,l:longint; function add:longint;begin inc(tot); exit(tot);end; procedure sinsert(var x:longint;y,z:longint);var left,right,mid,old:longint;begin if x=0 then x:=add; old:=x; left:=1; right:=n; while left<=right do begin mid:=(left+right)>>1; inc(size[x],z); if left=right then break; if y<=mid then begin right:=mid; if lson[x]=0 then lson[x]:=add; x:=lson[x]; end else begin left:=mid+1; if rson[x]=0 then rson[x]:=add; x:=rson[x]; end; end; x:=old;end; procedure binsert(x,l,r,tl,tr,tc:longint);var mid:longint;begin if (tl=l) and (tr=r) then begin sinsert(tree[x].mark,tc,1); exit; end; mid:=(l+r)>>1; sinsert(tree[x].all,tc,tr-tl+1); if tl>mid then binsert(x<<1+1,mid+1,r,tl,tr,tc) else if tr<=mid then binsert(x<<1,l,mid,tl,tr,tc) else begin binsert(x<<1,l,mid,tl,mid,tc); binsert(x<<1+1,mid+1,r,mid+1,tr,tc); end;end; procedure before(x,l,r,tl,tr:longint);var mid:longint;begin inc(sum); root1[sum]:=tree[x].mark; root2[sum]:=tr-tl+1; if (tl=l) and (tr=r) then begin inc(sum); root1[sum]:=tree[x].all; root2[sum]:=1; exit; end; mid:=(l+r)>>1; if tl>mid then before(x<<1+1,mid+1,r,tl,tr) else if tr<=mid then before(x<<1,l,mid,tl,tr) else begin before(x<<1,l,mid,tl,mid); before(x<<1+1,mid+1,r,mid+1,tr); end;end; procedure query(x,y,z:longint);var left,right,now,mid:longint;begin sum:=0; before(1,1,n,x,y); left:=1; right:=n; while left>1; for i:=1 to sum do now:=size[rson[root1[i]]]*root2[i]+now; if now 0 do begin dec(m); readln(i,j,k,l); if i=1 then binsert(1,1,n,j,k,l) else query(j,k,l); end; readln; readln;end.
数组开小竟然wa了两次。