//==========================
蒟蒻Macaulish：http://www.cnblogs.com/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=;
var
tree:array[..maxn]of arr;
size,lson,rson,root1,root2:array[..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= then x:=add;
old:=x;
left:=;
right:=n;
while left<=right do begin
mid:=(left+right)>>;
inc(size[x],z);
if left=right then break;
if y<=mid then begin
right:=mid;
if lson[x]= then lson[x]:=add;
x:=lson[x];
end
else begin
left:=mid+;
if rson[x]= 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,);
exit;
end;
mid:=(l+r)>>;
sinsert(tree[x].all,tc,tr-tl+);
if tl>mid then binsert(x<<+,mid+,r,tl,tr,tc)
else
if tr<=mid then binsert(x<<,l,mid,tl,tr,tc)
else begin
binsert(x<<,l,mid,tl,mid,tc);
binsert(x<<+,mid+,r,mid+,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+;
if (tl=l) and (tr=r) then begin
inc(sum);
root1[sum]:=tree[x].all;
root2[sum]:=;
exit;
end;
mid:=(l+r)>>;
if tl>mid then before(x<<+,mid+,r,tl,tr)
else
if tr<=mid then before(x<<,l,mid,tl,tr)
else begin
before(x<<,l,mid,tl,mid);
before(x<<+,mid+,r,mid+,tr);
end;
end; procedure query(x,y,z:longint);
var
left,right,now,mid:longint;
begin
sum:=;
before(,,n,x,y);
left:=;
right:=n;
while left<right do begin
now:=;
mid:=(left+right)>>;
for i:= to sum do
now:=size[rson[root1[i]]]*root2[i]+now;
if now<z then begin
dec(z,now);
right:=mid;
for i:= to sum do
root1[i]:=lson[root1[i]];
end
else begin
left:=mid+;
for i:= to sum do
root1[i]:=rson[root1[i]];
end;
end;
writeln(left);
end; begin
readln(n,m);
while m> do begin
dec(m);
readln(i,j,k,l);
if i= then binsert(,,n,j,k,l)
else query(j,k,l);
end;
readln;
readln;
end.
数组开小竟然wa了两次。