Program poj3468;
const
maxn=100000;
maxq=100000;
var
n,m,i,j,k:longint;
lazy,t:array[1..maxn*8] of int64;
c:char;
Procedure pushup(root:longint);
begin
t[root]:=t[root*2]+t[root*2+1];
end;
Procedure build(l,r,root:longint);
var
m:longint;
begin
if (l=r) then
begin
read(t[root]);
exit;
end;
m:=(l+r) shr 1;
build(l,m,root*2);
build(m+1,r,root*2+1);
pushup(root);
end;
Procedure Pushdown(l,r,root:longint);
var
m:longint;
begin
m:=(l+r) shr 1;
if (lazy[root]=0) then exit;
inc(lazy[root shl 1],lazy[root]);
inc(lazy[root shl 1+1],lazy[root]);
inc(t[root shl 1],lazy[root]*(m-l+1));
inc(t[root shl 1+1],lazy[root]*(r-(m+1)+1));
lazy[root]:=0;
end;
Procedure update(l,r,nowl,nowr,root,cost:longint);
var
m:longint;
begin
if (l<=nowl) and (nowr<=r) then
begin
inc(lazy[root],cost);
inc(t[root],(nowr-nowl+1)*cost);
exit;
end;
pushdown(nowl,nowr,root);
m:=(nowl+nowr) shr 1;
if (l<=m) then update(l,r,nowl,m,root*2,cost);
if (m+1<=r) then update(l,r,m+1,nowr,root*2+1,cost);
pushup(root);
end;
function query(l,r,nowl,nowr,root:longint):int64;
var
m:longint;
res:int64;
begin
if (l<=nowl) and (nowr<=r) then
begin
exit(t[root]);
end;
pushdown(nowl,nowr,root);
m:=(nowl+nowr) shr 1;
res:=0;
if (l<=m) then res:=res+query(l,r,nowl,m,root*2);
if (m+1<=r) then res:=res+query(l,r,m+1,nowr,root*2+1);
exit(res);
end;
begin
readln(n,m);
fillchar(lazy,sizeof(lazy),0);
build(1,n,1);
readln;
while (m>0) do
begin
read(c);
if c='Q' then
begin
readln(i,j);
writeln(query(i,j,1,n,1));
end
else
begin
readln(i,j,k);
update(i,j,1,n,1,k);
end;
dec(m);
end;
end.
Program p2777;
const
maxl=100000;
maxt=30;
maxo=100000;
var
l,t,o,i,j,k:longint;
col:array[1..maxl*10] of longint;
c:char;
x,y,color:longint;
visit:array[1..maxt] of boolean;
procedure build(l,r,root:longint);
var
mid:longint;
begin
if l=r then
begin
col[root]:=1;
exit;
end;
mid:=(l+r) shr 1;
build(l,mid,root shl 1);
build(mid+1,r,root shl 1+1);
col[root]:=1;
end;
procedure swap(var a,b:longint);
var
p:longint;
begin
p:=a;a:=b;b:=p;
end;
procedure detate(l,r,sonl,sonr,root,color:longint);
var
i,j,mid:longint;
begin
mid:=(l+r) shr 1;
if l=r then
begin
col[root]:=color;
exit;
end;
if (sonl<=l) and (r<=sonr) then
begin
col[root]:=color;
exit;
end;
if col[root]>0 then
begin
col[root*2]:=col[root];
col[root*2+1]:=col[root];
col[root]:=-1;
end;
if not((mid<sonl) or (sonr<l)) then detate(l,mid,sonl,sonr,root shl 1,color);
if not((r<sonl) or (sonr<mid+1)) then detate(mid+1,r,sonl,sonr,root shl 1+1,color);
end;
function quere(l,r,sonl,sonr,root:longint):longint;
var
mid,i,j:longint;
begin
quere:=0;
mid:=(l+r) shr 1;
if col[root]>0 then
begin
if not(visit[col[root]]) then
begin
visit[col[root]]:=true;
exit(1);
end;
exit(0);
end;
if not((mid<sonl) or (sonr<l)) then inc(quere,quere(l,mid,sonl,sonr,root shl 1));
if not((r<sonl) or (sonr<mid+1)) then inc(quere,quere(mid+1,r,sonl,sonr,root shl 1+1));
end;
begin
readln(l,t,o);
build(1,l,1);
for i:=1 to o do
begin
read(c);
if c='C' then
begin
readln(x,y,color);
if x>y then swap(x,y);
detate(1,l,x,y,1,color);
end
else
begin
readln(x,y);
if x>y then swap(x,y);
fillchar(visit,sizeof(visit),false);
writeln(quere(1,l,x,y,1));
end;
end;
end.
Program P2828;
const
maxn=200000;
var
n,i,j:longint;
pos,val:array[1..maxn] of longint;
sum:array[1..maxn*10] of longint;
ans:array[1..maxn] of longint;
procedure pushup(root:longint);
begin
sum[root]:=sum[root*2]+sum[root*2+1];
end;
procedure build(l,r,root:longint);
var
mid:longint;
begin
if l=r then
begin
sum[root]:=1;
exit;
end;
mid:=(l+r) shr 1;
build(l,mid,root*2);
build(mid+1,r,root*2+1);
pushup(root);
end;
procedure decr(l,r,root,node:longint);
var
mid:longint;
begin
if l=r then
begin
dec(sum[root]);
exit;
end;
mid:=(l+r) shr 1;
if (node<=mid) then decr(l,mid,root shl 1,node)
else decr(mid+1,r,root shl 1+1,node);
pushup(root);
end;
function find(l,r,root,value:longint):longint;
var
mid:longint;
begin
mid:=(l+r) shr 1;
if l=r then
begin
decr(1,n,1,l);
exit(l);
end;
if (sum[root shl 1]>=value) then exit(find(l,mid,root shl 1,value))
else exit(find(mid+1,r,root shl 1+1,value-sum[root shl 1]));
end;
begin
while not seekeof do
begin
read(n);
for i:=1 to n do read(pos[i],val[i]);
build(1,n,1);
for i:=n downto 1 do
begin
ans[find(1,n,1,pos[i]+1)]:=val[i];
end;
for i:=1 to n-1 do write(ans[i],' ');
writeln(ans[n]);
end;
end.
Program P2528;
const
maxn=10000;
maxr=10000000;
var
t,n,i,j,k:longint;
a,b,v:array[1..maxn*2] of longint;
h:array[1..maxr] of longint;
col:array[1..maxn*100] of longint;
visit:array[1..maxn*2] of boolean;
procedure qsort(l,r:longint);
var
i,j,m,p:longint;
begin
i:=l;
j:=r;
m:=v[(l+r) div 2];
repeat
while v[i]<m do inc(i);
while v[j]>m do dec(j);
if i<=j then
begin
p:=v[i];
v[i]:=v[j];
v[j]:=p;
inc(i);
dec(j);
end;
until i>j;
if l<j then qsort(l,j);
if i<r then qsort(i,r);
end;
procedure update(l,r,sonl,sonr,root,color:longint);
var
i,j,k,mid:longint;
begin
mid:=(l+r) shr 1;
if (sonl<=l) and (r<=sonr) then
begin
col[root]:=color;
exit;
end;
if (col[root]>=0) then
begin
col[root*2]:=col[root];
col[root*2+1]:=col[root];
col[root]:=-1;
end;
if not((mid<sonl) or (sonr<l)) then update(l,mid,sonl,sonr,root*2,color);
if not((r<sonl) or (sonr<mid+1)) then update(mid+1,r,sonl,sonr,root*2+1,color);
end;
function dfs(l,r,root:longint):longint;
var
i,j,mid:longint;
begin
mid:=(l+r) shr 1;
if col[root]=0 then exit(0);
if col[root]>0 then
begin
if not(visit[col[root]]) then
begin
visit[col[root]]:=true;
exit(1);
end
else exit(0);
end;
exit(dfs(l,mid,root*2)+dfs(mid+1,r,root*2+1));
end;
begin
read(t);
while t>0 do
begin
dec(t);
read(n);
for i:=1 to n do
begin
read(a[i],b[i]);
v[i]:=a[i];
v[n+i]:=b[i];
end;
qsort(1,2*n);
j:=1;
for i:=2 to 2*n do
if v[i]<>v[i-1] then
begin
inc(j);
v[j]:=v[i];
end;
for i:=1 to j do h[v[i]]:=i;
fillchar(col,sizeof(col),0);
for i:=1 to n do
begin
update(1,j,h[a[i]],h[b[i]],1,i);
end;
fillchar(visit,sizeof(visit),false);
writeln(dfs(1,j,1));
end;
end.