{謹供鄙視}
Treap版NOIP“明明的亂數”：
明明的亂數
明明想在學校中請一些同學一起做一項問卷調查，為了實驗的客觀性，他先用電腦生成了N個1到1000之間的隨機整數（N≤100），對於其中重複的數字，只保留一個，把其餘相同的數去掉，不同的數對應著不同的學生的學號。然後再把這些數從小到大排序，按照排好的順序去找同學做調查。請你協助明明完成“去重”與“排序”的工作。
輸入說明 ：
每組輸入有2行，第1行為1個正整數，表示所生成的亂數的個數：N
第2行有N個用空格隔開的正整數，為所產生的亂數。
輸出說明 ：
每組輸出也是2行，第1行為1個正整數M，表示不相同的亂數的個數。第2行為M個用空格隔開的正整數，為從小到大排好序的不相同的亂數。
範例輸入 ：
10
20 40 32 67 40 20 89 300 400 15
範例輸出 ：8
15 20 32 40 67 89 300 400
{TASK: 明明的亂數
ID: phoeagon
For: ***
LANG: PASCAL}
type
node=^link;
link=record
num,p,yy:longint;
lc,rc:node;
end;
var
null,root:^link;
n,count:longint; ou:boolean;
function leftr(t:node):node;
begin
leftr:=t^.lc;
t^.lc:=leftr^.rc;
leftr^.rc:=t;
end;
function rightr(t:node):node;
begin
rightr:=t^.rc;
t^.rc:=rightr^.lc;
rightr^.lc:=t;
end;
function insert(x:longint;t:node):node;
begin
if t=null then
begin
new(t);t^.num:=x;
t^.p:=random(maxint);
t^.lc:=null;
t^.rc:=null;
t^.yy:=1;
inc(count);
end
else if x=t^.num then
inc(t^.yy)
else if x<t^.num then
begin
t^.lc:=insert(x,t^.lc);
if t^.lc^.p<t^.p then
t:=leftr(t);
end
else if x>t^.num then
begin
t^.rc:=insert(x,t^.rc);
if t^.rc^.p<t^.p then
t:=rightr(t);
end;
insert:=t;
end;
procedure search(x:node);
begin
if x=null then
exit
else begin
search(x^.lc);
if not ou then begin
ou:=true;
write(x^.num);
end
else write(' ',x^.num);
//write(x^.num{,' ',x^.yy});
search(x^.rc);
end;
end;
procedure work;
var
i,n,a:longint; tmproot:node;
begin
read(n);{new(tt);}
{read(a);
root:=insert(a,root);} //tmproot:=root;
for i:=1 to n do
begin
read(a);
root:=insert(a,root);
//insert(a,null);
end;
writeln(count);
search(root);
end;
begin
randomize; ou:=false;
new(null);
null^.p:=maxlongint;
null^.lc:=null; null^.yy:=0;
null^.rc:=null;
root:=null;
work;
end.
離散化版“校門外的樹”（NOIP 2005）
內容 ：
某校大門外長度為L的馬路上有一排樹，每兩棵相鄰的樹之間的間隔都是1米。我們可以把馬路看成一個數軸，馬路的一端在數軸0的位置，另一端在L的位置；數軸上的每個整數點，即0，1，2，……，L，都種有一棵樹。
由於馬路上有一些區域要用來建地鐵。這些區域用它們在數軸上的起始點和終止點表示。已知任一區域的起始點和終止點的座標都是整數，區域之間可能有重合的部分。現在要把這些區域中的樹（包括區域端點處的兩棵樹）移走。你的任務是計算將這些樹都移走後，馬路上還有多少棵樹。
輸入說明 ：
每組輸入的第一行有兩個整數L（1 <= L <= 10000）和 M（1 <= M <= 100），L代表馬路的長度，M代表區域的數目，L和M之間用一個空格隔開。接下來的M行每行包含兩個不同的整數，用一個空格隔開，表示一個區域的起始點和終止點的座標。
輸出說明 ：
每組輸出包括一行，這一行只包含一個整數，表示馬路上剩餘的樹的數目。
範例輸入 ：
500 3
150 300
100 200
470 471
範例輸出 ：
298
{
Prob: 校門外的樹（Noip2005）
演算法：離散化
}
const
maxm=110;
type
node=record
st,ed:longint;
//stn,edn:longint;
end;
link=record
x:longint;
add:^longint;
end;
var
d:array[0..2*maxm+2]of boolean;
ct:array[0..2*maxm+2]of longint;
pt:array[0..2*maxm]of node;
tmp:array[0..2*maxm+2]of link;
n,m,top:longint;
procedure init;
var
i:longint;
begin
read(n,m);top:=1;tmp[top].x:=0;{inc(top);tmp[top].x:=n;}
tmp[m*2+2].x:=n;
for i:=1 to m do
begin
read(pt.st,pt.ed);
inc(top);tmp[top].x:=pt.st;tmp[top].add:[email protected];
inc(top);tmp[top].x:=pt.ed;tmp[top].add:[email protected];
end;
end;
procedure qsort(l,r:longint);
var
i,j,x1:longint;
y:link;
begin
i:=random(r-l)+l;
y:=tmp;tmp:=tmp[(l+r)div 2];tmp[(l+r)div 2]:=y;
i:=l;j:=r;x1:=tmp[(l+r)div 2].x;
repeat
while (tmp.x<x1) do inc(i);
while (tmp[j].x>x1) do dec(j);
if not(i>j)then
begin
y:=tmp;tmp:=tmp[j];tmp[j]:=y;
inc(i);dec(j);
end;
until i>=j;
if i<r then qsort(i,r);
if l<j then qsort(l,j);
end;
{procedure selectionsort(l,r:longint);
var
i,j,k:longint;t:link;
begin
for i:=l to r-1 do
begin
k:=i;
for j:=i+1 to r do
if (tmp[j].x<tmp[k].x)
{or((tmp[j].x=tmp[k].x)and(tmp[j].add<tmp[k].add))}
then
k:=j;
t:=tmp;tmp:=tmp[k];tmp[k]:=t;
end;
end;}
procedure work;
var
i,j,count:longint;x1:^longint;
begin
count:=0;
for i:=1 to top do
ct:=tmp.x-tmp[i-1].x;
for i:=2 to top do
begin
x1:=tmp.add;
x1^:=i;
end;
for i:=1 to m do
for j:=pt.st+1 to pt.ed do
d[j]:=true;
{for i:=1 to top do
if not dthen
inc(count,ct{-ct[i-1]});
writeln(count); }
for i:=1 to top do
if dthen
if not d[i-1]then
inc(count,ct+1)
else inc(count,ct);
writeln(n+1-count);
end;
begin
init;
qsort(2,top);
work;
end.
校門外的樹（tree.pas/c/cpp）
某校大門外長度為L的馬路上有一排樹，每兩棵相鄰的樹之間的間隔都是1米。我們可以把馬路看成一個數軸，馬路的一端在數軸0的位置，另一端在L的位置；數軸上的每個整數點，即0，1，2，……，L，都種有一棵樹。
由於馬路上有一些區域要用來建地鐵。這些區域用它們在數軸上的起始點和終止點表示。已知任一區域的起始點和終止點的座標都是整數，區域之間可能有重合的部分。現在要把這些區域中的樹（包括區域端點處的兩棵樹）移走。你的任務是計算將這些樹都移走後，馬路上還有多少棵樹。
輸入說明 ：
每組輸入的第一行有兩個整數L（1 <= L <= 10000）和 M（1 <= M <= 100），L代表馬路的長度，M代表區域的數目，L和M之間用一個空格隔開。接下來的M行每行包含兩個不同的整數，用一個空格隔開，表示一個區域的起始點和終止點的座標。
輸出說明 ：
每組輸出包括一行，這一行只包含一個整數，表示馬路上剩餘的樹的數目。
範例輸入 ：
500 3
150 300
100 200
470 471
範例輸出 ：
298
提示 ：
對於20%的資料，區域之間沒有重合的部分；對於其他的資料，區域之間有重合的情況。
出處 ：
NOIP2005 普及組
校門外的樹——Segment Tree版：
{
NOIP 校門外的樹
agorithm: simulation
data Structure: Segment_Tree (According to _gXX, point tree)
Many thanks to _gXX, who generously offered much assistance with the PKU 2777.
by: phoeagon
For y^3!
}
const
lim=10000;
type
node=record
hd,ed,ct:longint;
f:boolean;
end;
var
tree:array[0..2 shl 15]of node;
n,m:longint;
procedure build(a,b,nd:longint);
begin
tree[nd].hd:=a;tree[nd].ed:=b;tree[nd].ct:=0;tree[nd].f:=false;
if a<b then
begin
build(a,(a+b)shr 1,nd*2);
build((a+b)shr 1+1,b,nd*2+1);
end;
end;
procedure del(a,b,nd:longint);
var
mid:longint;
begin
if tree[nd].ct=tree[nd].ed-tree[nd].hd+1 then
exit
else if (a=tree[nd].hd)and(b=tree[nd].ed)then
tree[nd].ct:=b-a+1
else
begin
mid:=(tree[nd].hd+tree[nd].ed) shr 1;
if b<=mid then
del(a,b,nd*2)
else if a>=mid+1 then
del(a,b,nd*2+1)
else
begin
del(a,mid,nd*2);
del(mid+1,b,nd*2+1);
end;
tree[nd].ct:=tree[nd*2].ct+tree[nd*2+1].ct;
end;
end;
function calc(a,b,nd:longint):longint; //not actually needed, all the
//queries are about the root node
var
mid:longint;
begin
if tree[nd].ct=0 then
exit(0)
else if tree[nd].ct=tree[nd].ed-tree[nd].hd+1 then
exit(b-a+1)
else if (tree[nd].hd=a)and
(tree[nd].ed=b)then
exit(tree[nd].ct)
else begin
mid:=(tree[nd].hd+tree[nd].ed)shr 1;
if b<=mid then
exit(calc(a,b,nd*2))
else if a>mid then
exit(calc(a,b,nd*2))
else exit(calc(a,mid,nd*2)+calc(mid+1,b,nd*2+1));
end;
end;
procedure work;
var
i,a,b:longint;
begin
read(n,m);
build(0,n,1);
for i:=1 to m do
begin
read(a,b);
del(a,b,1);
end;
//writeln(n+1-tree[1].ct);
writeln(n+1-calc(0,n,1));
end;
begin
work;
end.
|
