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

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ3781]小B的询问  

2015-01-05 19:16:24|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3781: 小B的询问

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 184  Solved: 126
[Submit][Status]

Description

小B有一个序列,包含N个1~K之间的整数。他一共有M个询问,每个询问给定一个区间[L..R],求Sigma(c(i)^2)的值,其中i的值从1到K,其中c(i)表示数字i在[L..R]中的重复次数。小B请你帮助他回答询问。

Input

第一行,三个整数N、M、K。
第二行,N个整数,表示小B的序列。
接下来的M行,每行两个整数L、R。

Output

M行,每行一个整数,其中第i行的整数表示第i个询问的答案。

Sample Input

6 4 3
1 3 2 1 1 3
1 4
2 6
3 5
5 6

Sample Output

6
9
5
2

HINT

对于全部的数据, 1<=N MK<=50000

Solution

裸的莫队。一看N=5W就知道可以不用写log做法了

在做莫队的时候,需要写一个数据结构,支持单点修改,区间求平方和,于是无脑线段树,发现跑了倒一。。。

其实有插入和删除都是O(1)的做法,考虑x原来有c次出现,当c+1时,ans+=(c+1)^2-c^2=2c+1;当c-1时,ans-=c^2-(c-1)^2=2c-1。于是直接加减就好了。

Code

/**************************************************************
    Problem: 3781
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:1184 ms
    Memory:2184 kb
****************************************************************/
 
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
int aa;char ch;int F(){
    while(ch=getchar(),ch<'0'||ch>'9');aa=ch-'0';
    while(ch=getchar(),ch>='0'&&ch<='9')aa=aa*10+ch-'0';return aa;
}
#define N 50010
int cnt[N],d,n,m,lim,k,i,j,a[N],u;long long ans[N],v;
struct Q{int l,r,n;}q[N];
bool operator<(const Q&i,const Q&j){return i.l/k<j.l/k||i.l/k==j.l/k&&i.r<j.r;}
int main(){
    n=F(),m=F(),lim=F();k=sqrt(n)+1;
    for(i=0;i<n;i++)a[i]=F();
    for(i=1;i<=m;i++)
    {
        q[i]=(Q){F()-1,F()-1,i};
        if(q[i].l/k==q[i].r/k)
        {
            for(j=q[i].l;j<=q[i].r;j++)ans[i]+=(cnt[a[j]]<<1|1),cnt[a[j]]++;
            for(j=q[i].l;j<=q[i].r;j++)cnt[a[j]]--;
            q[i].n=-1;
        }
    }
    std::sort(q+1,q+1+m);
    for(i=1;i<=m;i=j+1)
    {
        int l,r;memset(cnt,0,sizeof(cnt));
        for(j=i;j<=m&&q[i].l/k==q[j].l/k;j++);j--;
        for(v=0,r=q[i].l/k*k+k,l=r-1,u=i;u<=j;u++)if(q[u].n!=-1)
        {
            for(;r<=q[u].r;r++)v+=(cnt[a[r]]<<1|1),cnt[a[r]]++;
            if(l>=q[u].l)for(;l>=q[u].l;l--)v+=(cnt[a[l]]<<1|1),cnt[a[l]]++;
            else if(l<q[u].l-1)for(;l<q[u].l-1;l++)cnt[a[l+1]]--,v-=(cnt[a[l+1]]<<1|1);
            ans[q[u].n]=v;
        }
    }
    for(i=1;i<=m;i++)printf("%lld\n",ans[i]);
}
  评论这张
 
阅读(28)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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