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

n+e

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

 
 
 

日志

 
 

[BZOJ3236/3809][Ahoi2013]作业  

2015-01-05 20:02:23|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3236: [Ahoi2013]作业

Time Limit: 100 Sec  Memory Limit: 512 MB
Submit: 765  Solved: 283
[Submit][Status]

Description

Input

Output

Sample Input

3 4
1 2 2
1 2 1 3
1 2 1 1
1 3 1 3
2 3 2 3

Sample Output

2 2
1 1
3 2
2 1

HINT

N=100000,M=1000000

Solution

对于第一问,主席树就可以搞定了。

难就难在第二问,想不出log的做法。后来听讲评是莫队,然后就忘得差不多了


O(n^1.5)做法:对于询问,分成sqrt(n)块,按照莫队直接做。

在莫队里面可以用一个数据结构,维护区间内的数出现的次数,以及这个数是否出现。显然可以用线段树或者树状数组来维护。插入:log & 删除:log

不过既然都莫队了,再来一个分块又不会怎么样。由于分块的插入是O(1),询问是O(sqrt(n)),莫队的效率是插入:O(sqrt(n)),查询O(1),所以总的复杂度是插入:O(sqrt(n)),删除:O(sqrt(n)),总效率:O(m*sqrt(n))。

还跑得挺快的。。。

Code

/**************************************************************
    Problem: 3236
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:21992 ms
    Memory:29340 kb
****************************************************************/
 
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<ctime>
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 100010
#define M 1000010
int n,m,t,a[N],cnt[N],ans0[M],ans1[M],k0[1000],k1[1000],l,r,i,w[N];
struct D{
    int l,r,a,b,n;
    bool operator<(const D&i)const{
        if(w[l]==w[i.l])return r<i.r;
        return l<i.l;
    }
}q[M];
int query(int l,int r,int id){
    int ans=0,i;
    if(w[l]==w[r]){
        for(i=l;i<=r;i++)
        if(cnt[i])ans0[id]+=cnt[i],ans1[id]++;
    }
    else{
        for(i=w[l]*t-1;i>=l;i--)if(cnt[i])ans1[id]++,ans0[id]+=cnt[i];
        for(i=w[r]*t-t;i<=r;i++)if(cnt[i])ans1[id]++,ans0[id]+=cnt[i];
        for(i=w[l]+1;i<w[r];i++)ans1[id]+=k1[i],ans0[id]+=k0[i];
    }
}
inline void add(int x){
    if(++k0[w[x]],++cnt[x]==1)k1[w[x]]++;
}
inline void del(int x){
    if(--k0[w[x]],--cnt[x]==0)k1[w[x]]--;
}
int main()
{
    for(n=F(),m=F(),t=sqrt(n/2),i=1;i<=n;i++)a[i]=F(),w[i]=i/t+1;
    for(i=1;i<=m;i++)q[i]=(D){F(),F(),F(),F(),i};
    std::sort(q+1,q+m+1);
    for(i=l=1;i<=m;i++)
    {
        for(;l<q[i].l;del(a[l++]));
        for(;l>q[i].l;add(a[--l]));
        for(;r<q[i].r;add(a[++r]));
        for(;r>q[i].r;del(a[r--]));
        query(q[i].a,q[i].b,q[i].n);
    }
    for(i=1;i<=m;i++)printf("%d %d\n",ans0[i],ans1[i]);
}
  评论这张
 
阅读(175)| 评论(6)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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