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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【NBUT1457】【莫队算法】【Sona】  

2014-03-25 09:56:08|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
    题目大意(英语渣搜到的...),给乃一个数列,询问区间所有数出现次数的立方和。
    无修改果然是莫队算法的天下了.....这个只需要先离散化然后按照莫队算法的方向暴力就可以了....10^5刚好可以勉强过....(加上离散化的二分查找...)
    话说这个OJ貌似没了??咱不知道去哪里测试...
================================

program nbut1457;
const maxn=200010;
type point=record
     x,y,num:longint;
     end;
     arr=array[0..maxn]of point;

var ask:array[0..maxn]of point;
    a,w,pos,st:array[0..maxn]of longint;
    ans,num:array[0..maxn]of int64;
    n,q:longint;

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

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

function find(x,n:longint):longint;
var l,r,mid:longint;
begin
  l:=1;r:=n;
  while l<r do
   begin
     mid:=(l+r)shr 1;
     if w[mid]=x then exit(mid);
     if w[mid]<x then l:=mid+1
                 else r:=mid-1;
   end;
  exit(l);
end;

procedure init;
var i,j,m,k,l,r,wh,sum:longint;
    tmp:int64;
begin
  read(n);
  m:=trunc(sqrt(n));
  j:=1;k:=1;
  for i:=1 to n do
   begin
    read(a[i]);
    w[i]:=a[i];
    pos[i]:=k;
    inc(j);
    if j>m then
     begin
       j:=1;
       inc(k);
     end;
   end;
  qsort(1,n);
  sum:=1;
  for i:=2 to n do
   if w[i]<>w[sum] then
    begin
      inc(sum);
      w[sum]:=w[i];
    end;
  read(q);
  for i:=1 to q do
   begin
    read(ask[i].x,ask[i].y);
    ask[i].num:=i;
   end;
  qsort(1,q,ask);
  tmp:=0;l:=1;r:=0;
  fillchar(num,sizeof(num),0);
  for i:=1 to q do
   begin
     while r<ask[i].y do
      begin
        inc(r);
        wh:=find(a[r],sum);
        tmp:=tmp-num[wh]*num[wh]*num[wh];
        inc(num[wh]);
        tmp:=tmp+num[wh]*num[wh]*num[wh];
      end;
     while r>ask[i].y do
      begin
        wh:=find(a[r],sum);
        tmp:=tmp-num[wh]*num[wh]*num[wh];
        dec(num[wh]);
        tmp:=tmp+num[wh]*num[wh]*num[wh];
        dec(r);
      end;
     while l<ask[i].x do
      begin
        wh:=find(a[l],sum);
        tmp:=tmp-num[wh]*num[wh]*num[wh];
        dec(num[wh]);
        tmp:=tmp+num[wh]*num[wh]*num[wh];
        inc(l);
      end;
     while l>ask[i].x do
      begin
        dec(l);
        wh:=find(a[l],sum);
        tmp:=tmp-num[wh]*num[wh]*num[wh];
        inc(num[wh]);
        tmp:=tmp+num[wh]*num[wh]*num[wh];
      end;
     ans[ask[i].num]:=tmp;
   end;
  for i:=1 to q do
   writeln(ans[i]);
end;

begin
  init;
end.


  评论这张
 
阅读(39)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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