bzoj 2038 莫队算法
2024-10-14 07:32:19
莫队算法，具体的可以看10年莫涛的论文。
大题思路就是假设对于区间l,r我们有了一个答案，那么对于区间l,r+1，我们
可以暴力的转移一个答案，那么对于区间l1,r1和区间l2,r2，需要暴力处理
的部分就是|r1-r2|+|l1-l2|如果将l看成x，r看成r，得到的暴力部分就是manhattan距离
那么我们将所有的询问，构成一张二维图，可以从一个点转移到另一个点，且总manhattan距离
尽可能的小，所以可以建立一颗manhattan mst，这样的话就可以得到最优的转移，但是实际来说
搞定一个manhattan mst需要的时间不小，我们可以不要最优解，将询问按l分块，只需要做到在每个
块中尽可能的优就行了，所以每个块中可以根据r排序，然后搞就行了
经莫队证明，这个算法的复杂度上界大概是o(n^1.5)
/**************************************************************
Problem:
User: BLADEVIL
Language: Pascal
Result: Accepted
Time: ms
Memory: kb
****************************************************************/
//By BLADEVIL
type
rec =record
l, r, w, s :longint;
end;
var
n, m :longint;
c, size :array[..] of int64;
len :longint;
a :array[..] of rec;
now :longint;
col, ans :array[..] of int64;
all, num :int64;
procedure swap(var a,b:longint);
var
c :longint;
begin
c:=a; a:=b; b:=c;
end;
procedure swap_rec(var a,b:rec);
var
c :rec;
begin
c:=a; a:=b; b:=c;
end;
function gcd(a,b:int64):int64;
begin
if a<b then exit(gcd(b,a)) else
if b= then exit(a) else exit(gcd(b,a mod b));
end;
procedure qs(low,high:longint);
var
i, j, xx, yy :longint;
begin
i:=low; j:=high; xx:=a[(i+j) div ].w;
yy:=a[(i+j) div ].r;
while i<j do
begin
while (a[i].w<xx) or (a[i].w=xx) and (a[i].r<yy) do inc(i);
while (a[j].w>xx) or (a[j].w=xx) and (a[j].r>yy) do dec(j);
if i<=j then
begin
swap_rec(a[i],a[j]);
inc(i); dec(j);
end;
end;
if i<high then qs(i,high);
if j>low then qs(low,j);
end;
procedure init;
var
i :longint;
begin
read(n,m);
for i:= to n do read(c[i]);
len:=trunc(sqrt(m));
for i:= to m do
begin
read(a[i].l,a[i].r);
if a[i].l>a[i].r then swap(a[i].l,a[i].r);
size[i]:=a[i].r-a[i].l+;
a[i].w:=a[i].l div len+;
a[i].s:=i;
end;
qs(,m);
end;
procedure main;
var
i, j :longint;
begin
i:=;
while i<=m do
begin
now:=a[i].w;
fillchar(col,sizeof(col),);
for j:=a[i].l to a[i].r do
begin
ans[a[i].s]:=ans[a[i].s]+*(col[c[j]]);
col[c[j]]:=col[c[j]]+;
end;
inc(i);
while a[i].w<=now do
begin
ans[a[i].s]:=ans[a[i-].s];
for j:=a[i-].r+ to a[i].r do
begin
ans[a[i].s]:=ans[a[i].s]+*(col[c[j]]);
col[c[j]]:=col[c[j]]+;
end;
if a[i-].l<a[i].l then
begin
for j:=a[i-].l to a[i].l- do
begin
col[c[j]]:=col[c[j]]-;
ans[a[i].s]:=ans[a[i].s]-*col[c[j]];
end;
end else
for j:=a[i].l to a[i-].l- do
begin
ans[a[i].s]:=ans[a[i].s]+*(col[c[j]]);
col[c[j]]:=col[c[j]]+;
end;
inc(i);
if i>m then break;
end;
end;
for i:= to m do
begin
if size[i]= then all:= else all:=size[i]*(size[i]-);
num:=gcd(ans[i],all);
writeln(ans[i] div num,'/',all div num);
end;
end;
begin
init;
main;
end.
最新文章
- NSSortDescriptor 的使用
- python包使用指南－创建虚拟环境
- iOS 真机调试不能连接网络的排错过程
- 深入浅出Mybatis系列（五）---TypeHandler简介及配置（mybatis源码篇）
- iphone按home键后，正在运行的程序是否退出了呢？
- windows 下双网卡在不同网络切换设置
- [C/C++]C++标准
- EntityFramework走马观花之CRUD（上）
- Spring中通配符
- C#--比较
- 关于ActionBar的向下兼容
- WinPython安装问题（pyzmq问题导致）
- Android:解决client从server上获取数据乱码的方法
- 【Linux配置】vim配置文件内容
- SSM 五：Spring核心概念
- 在java中写出完美的单例模式
- CodeForces 868F Yet Another Minimization Problem(决策单调性优化 + 分治)
- vim语法
- 【Dubbo 源码解析】01_Dubbo 设计简介
- 兼容低版本 ie 的思路