注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

z55250825

一只蒟蒻

 
 
 

日志

 
 

【BZOJ2038】【莫队算法】【小Z的袜子】  

2014-03-23 21:15:04|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
    首先orz ydc神犇的题解 题解君 ,貌似是搜索的题解中最详细的了...
    话说咱的袜子一般都是不乱放的233。 
    实际上就是考虑 从[l,r]转移到[l+1,r]或者(经ydc君提醒改成 “且”)[l,r+1]如果有O(1)(其实感觉只要转移就可以了,不必要O(1)也可以,只不过复杂度加上去而已)(这个转移需要一个支持插入元素删除元素以及统计信息的数据结构)的话,只需要考虑对于所有询问怎样转移即可。
    这个优化的想法其实就是想去求曼哈顿距离的MST。
    然后一个神奇的替代品就是分块,代码量骤减到考场的暴力级别!!!(话说咱打暴力经常手抖很长啊233)
    其实看ydc神犇的解释感觉挺怪异的....莫队算法挺像个暴力算法啊啊啊.....
    这题的O(1)的转移只要维护两个指针 L,R,然后维护一个num数组表示当前区间【L,R】某种颜色的出现次数。
===============================

program bzoj2038;
const maxn=50010;
type node=record
     x,y:int64;
     end;

var pos,ans:array[0..maxn]of node;
    num,a,st:array[0..maxn]of longint;
    n,m,w,tot:longint;

function gcd(a,b:int64):int64;
begin
  if b=0 then exit(a);
  exit(gcd(b,a mod b));
end;

procedure qsort(l,r:longint);
var i,j,x,y,w:longint;z:node;
begin
  i:=l;j:=r;
  x:=num[pos[(l+r)shr 1].x];
  y:=pos[(l+r)shr 1].y;
  repeat
    while (num[pos[i].x]<x)or((num[pos[i].x]=x)and(pos[i].y<y)) do inc(i);
    while (num[pos[j].x]>x)or((num[pos[j].x]=x)and(pos[j].y>y)) do dec(j);
    if i<=j then
     begin
       z:=pos[i];pos[i]:=pos[j];pos[j]:=z;
       w:=st[i];st[i]:=st[j];st[j]:=w;
       inc(i);dec(j);
     end;
  until i>j;
  if i<r then qsort(i,r);
  if j>l then qsort(l,j);
end;

procedure init;
var i,j:longint;
    ww,tmp,ll,rr:int64;
begin
  read(n,m);
  w:=trunc(sqrt(n));
  tot:=1;j:=0;
  for i:=1 to n do
   begin
     inc(j);
     if j=w+1 then
      begin
        inc(tot);
        j:=0;
      end;
     read(a[i]);
     num[i]:=tot;
   end;
  for i:=1 to m do
   begin
    read(pos[i].x,pos[i].y);
    st[i]:=i;
   end;
  qsort(1,m);
  fillchar(num,sizeof(num),0);
  tmp:=0;ll:=1;rr:=0;
  for i:=1 to m do
   begin
     while (rr<pos[i].y) do
      begin
        inc(rr);
        tmp:=tmp-num[a[rr]]*num[a[rr]];
        inc(num[a[rr]]);
        tmp:=tmp+num[a[rr]]*num[a[rr]];
      end;
     while (rr>pos[i].y) do
      begin
        tmp:=tmp-num[a[rr]]*num[a[rr]];
        dec(num[a[rr]]);
        tmp:=tmp+num[a[rr]]*num[a[rr]];
        dec(rr);
      end;
     while (ll<pos[i].x) do
      begin
        tmp:=tmp-num[a[ll]]*num[a[ll]];
        dec(num[a[ll]]);
        tmp:=tmp+num[a[ll]]*num[a[ll]];
        inc(ll);
      end;
     while (ll>pos[i].x) do
      begin
        dec(ll);
        tmp:=tmp-num[a[ll]]*num[a[ll]];
        inc(num[a[ll]]);
        tmp:=tmp+num[a[ll]]*num[a[ll]];
      end;
     ans[st[i]].x:=tmp-(rr-ll+1);
     ans[st[i]].y:=(rr-ll+1)*(rr-ll);
     ww:=gcd(ans[st[i]].x,ans[st[i]].y);
     ans[st[i]].x:=ans[st[i]].x div ww;
     ans[st[i]].y:=ans[st[i]].y div ww;
   end;
  for i:=1 to m do
   writeln(ans[i].x,'/',ans[i].y);
end;

begin
  init;
end.



  评论这张
 
阅读(78)| 评论(4)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017