数三角形 bzoj 3505
要知道一个公式就是(a,b)和(x,y)两点所成线段上面的整点数是gcd(a-x,b-y)-1，通过枚举原点到map上任意一点所能成的三角形，再平移，得到要去掉的三点共线的点对。
我当时弱智地弄了个O(n^6)的枚举，不过好歹还是对的拿了三十分。
= =满分程序和30分程序几乎一样长。
program triangle;
var m,n,i,j:integer;
ans,t:qword; function gcd(a,b:integer):integer;
begin
if a= then exit(b);
if b= then exit(a);
if a mod b= then exit(b) else exit(gcd(b,a mod b));
end; begin{main}
readln(m,n);
t:=(m+)*(n+);
ans:=t*(t-)*(t-) div ;
for i:= to m do
for j:= to n do
if not ((i=) and (j=)) then
begin
if (i=) or (j=) then ans:=ans-(gcd(i,j)-)*(m-i+)*(n-j+)
else ans:=ans-*(gcd(i,j)-)*(m-i+)*(n-j+);
end;
writeln(ans);
end.
Triangle
机械排序臂 bzoj 3506
那天早上还是写的O(n^2)骗的30分，不过这回30和100的代码长度就差远了…
7/2开始写这题，7/2当天晚上学习&码完splay，是对的，但是之后的lazy tag，没什么资料，C++的程序又看不太懂，我调了这么多天简直崩溃了好吗！最后发现是左子树注入tag的时候不应该直接赋值true而应该赋反，这一点在switch里面想到了，但是在主程序里没想到。对着sort1.in这个n=1000的输入文件我愣了好久啊，为什么输出的前80%是对的但是之后就有的对有的不对了呢。一开始我以为是树的fa啊，lc、rc啊没消除干净，导致被删的结点又重新回来，后来发现这也不是回事…
不过还好找到了错误所在，现在整个人心情爆好！！
200行的程序，况且这还不是完全的splay…弱渣的我到时候要好好背一下…
program sort3;
var n,i,root,c,x,t,temp:longint;
f,ff,loc,l,fa,lc,rc,da,tot:array[..] of longint;
lazy:array[..] of boolean; function dd(x,xloc,y,yloc:longint):boolean;
begin
if x<y then exit(true);
if (x=y) and (xloc<yloc) then exit(true);
exit(false);
end; function gg(x,xloc,y,yloc:longint):boolean;
begin
if x>y then exit(true);
if (x=y) and (xloc>yloc) then exit(true);
exit(false);
end; procedure qsort(l,r:longint);
var mid,mid_loc,i,j,temp:longint;
begin
i:=l;j:=r;mid:=f[(l+r) div ];mid_loc:=loc[(l+r) div ];
while i<=j do
begin
while dd(f[i],loc[i],mid,mid_loc) do inc(i);
while gg(f[j],loc[j],mid,mid_loc) do dec(j);
if i<=j then
begin
temp:=f[i];f[i]:=f[j];f[j]:=temp;
temp:=loc[i];loc[i]:=loc[j];loc[j]:=temp;
inc(i);dec(j);
end;
end;
if i<r then qsort(i,r);
if l<j then qsort(l,j);
end; procedure lrot(p:longint);
var q:longint;
begin
q:=fa[p];fa[p]:=fa[q];
if q=root then root:=p else
if q=lc[fa[q]] then lc[fa[q]]:=p else rc[fa[q]]:=p;
lc[q]:=rc[p];
if rc[p]<> then fa[rc[p]]:=q;
rc[p]:=q;
fa[q]:=p;
tot[q]:=tot[lc[q]]+tot[rc[q]]+;
tot[p]:=tot[lc[p]]+tot[rc[p]]+;
end; procedure rrot(p:longint);
var q:longint;
begin
q:=fa[p];fa[p]:=fa[q];
if q=root then root:=p else
if lc[fa[q]]=q then lc[fa[q]]:=p else
rc[fa[q]]:=p;
rc[q]:=lc[p];
if lc[p]<> then fa[lc[p]]:=q;
lc[p]:=q;
fa[q]:=p;
tot[q]:=tot[lc[q]]+tot[rc[q]]+;
tot[p]:=tot[lc[p]]+tot[rc[p]]+;
end; procedure switch(p:longint);
var t:longint;
begin
if lazy[p]=false then exit;
t:=lc[p];lc[p]:=rc[p];rc[p]:=t;
lazy[p]:=false;
lazy[lc[p]]:=not lazy[lc[p]];
lazy[rc[p]]:=not lazy[rc[p]];
end; procedure clear(p:longint);
begin
if p=root then
begin
if lazy[p] then switch(p);
exit;
end;
clear(fa[p]);
if lazy[p] then switch(p);
end; procedure splay(p:longint);
var t,tt:longint;
begin
while p<>root do
begin
if p=lc[fa[p]] then //p is lc
begin
if fa[p]=root then lrot(p) else
if fa[p]=lc[fa[fa[p]]] then
begin
lrot(fa[p]);lrot(p);
end
else
begin
lrot(p);rrot(p);
end;
end
else
begin
if fa[p]=root then rrot(p) else
if fa[p]=rc[fa[fa[p]]] then
begin
rrot(fa[p]);rrot(p);
end
else
begin
rrot(p);lrot(p);
end;
end;
end;
fa[p]:=;
end; procedure insert(x:longint);
var t,tt:longint;
begin
inc(c);
fa[c]:=;lc[c]:=;rc[c]:=;da[c]:=f[x];
if root= then
begin
root:=c;
tot[root]:=;
end
else
begin
t:=root;
repeat
begin
tt:=t;
if loc[x]<loc[t] then
begin
inc(tot[t]);
t:=lc[t];
end
else
begin
inc(tot[t]);
t:=rc[t];
end;
end;
until t=;
tot[x]:=;
if loc[x]<loc[tt] then lc[tt]:=c else rc[tt]:=c;
fa[c]:=tt;
splay(c);
end;
end; begin
//assign(input,'sort10.in');reset(input);
//assign(output,'sort10.out');rewrite(output);
fillchar(lazy,sizeof(lazy),false);
readln(n);
for i:= to n do
begin
read(f[i]);
loc[i]:=i;
end;
ff:=f;
qsort(,n);
for i:= to n do
begin
f[i]:=i;
end;
for i:= to n do
insert(i); //buildtree
for i:= to n do
begin
clear(i);
splay(i);
write(tot[lc[i]]+i,' ');
lazy[lc[i]]:=not lazy[lc[i]]; //oh no I wrote':=true' and debuged for days..
t:=lc[i];
if lazy[t] then switch(t);
while rc[t]<> do
begin
t:=rc[t];
if lazy[t] then switch(t);
end;
fa[rc[i]]:=;fa[lc[i]]:=;root:=lc[i];temp:=rc[i];tot[i]:=;
if lc[i]= then root:=rc[i];
rc[i]:=;lc[i]:=;fa[i]:=;
if t<> then
begin
clear(t);//from down to top then top to down
splay(t);
fa[temp]:=t;rc[t]:=temp;tot[t]:=tot[t]+tot[rc[t]];
end
end;
//close(input);close(output);
end.
Sort