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

n+e

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

 
 
 

日志

 
 

[BZOJ2453/2120]维护队列  

2014-12-01 20:31:19|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2453: 维护队列

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 212  Solved: 103
[Submit][Status]

Description

你小时候玩过弹珠吗?
小朋友A有一些弹珠,A喜欢把它们排成队列,从左到右编号为1到N。为了整个队列鲜艳美 观,小朋友想知道某一段连续弹珠中,不同颜色的弹珠有多少。当然,A有时候会依据个人喜好,替换队列中某个弹珠的颜色。但是A还没有学过编程,且觉得头脑 风暴太浪费脑力了,所以向你来寻求帮助。

Input

输入文件第一行包含两个整数N和M。
第二行N个整数,表示初始队列中弹珠的颜色。
接下来M行,每行的形式为“Q L R”或“R x c”,“Q L R”表示A想知道从队列第L个弹珠到第R个弹珠中,一共有多少不同颜色的弹珠,“R x c”表示A把x位置上的弹珠换成了c颜色。

Output

对于每个Q操作,输出一行表示询问结果。

Sample Input

2 3
1 2
Q 1 2
R 1 2
Q 1 2

Sample Output

2
1

HINT

对于100%的数据,有1 ≤ N ≤ 10000, 1 ≤ M ≤ 10000,小朋友A不会修改超过1000次,所有颜色均用1到10^6的整数表示。

Solution

10000*10000,暴力都能过,。。。

来一点不暴力的,分块。对于每个点,记录它之前离它最近出现过的颜色的编号。

查询[l,r]的话,相当于在新数组中查询编号<l的数有几个

于是就可以分块了。修改可以暴力查找要改哪几个点,再用sqrt(n)*log(sqrt(n))的时间更新(排序);查询小区间暴力,大区间在排序好的数组上二分。

还有更不暴力的——线段树套splay?外层的数据结构就是跟分块写法差不多,里层的要支持动态删点、加点、查询rank,好像只能用splay了。

表示写不出来= =只会YY

Code

/**************************************************************
    Problem: 2453
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:676 ms
    Memory:4880 kb
****************************************************************/
 
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
int aa;char ch,op;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 10010
int n,m,col[N],L[N],R[N],la[1000010],i,j,k,pre[N],ans,t[3],l,r,K;
void vio(int x,int y){for(int i=x;i<=y;i++)if(L[i]<l)ans++;}
void bin(int l,int r,int x){
    int mid,ol=l;
    for(r=std::min(r,n-1)+1;l<r;pre[mid=l+r>>1]>=x?r=mid:l=mid+1);
    ans+=l-ol;
}
void update(int x){
    int l=x*m,r=std::min(x*m+m-1,n-1);
    for(int i=l;i<=r;i++)pre[i]=L[i];
    std::sort(pre+l,pre+r+1);
}
int main(){
    memset(la,-1,sizeof(la));
    memset(L,-1,sizeof(L));
    memset(R,-1,sizeof(R));
    for(n=F(),K=F(),m=sqrt(n)+1,i=0;i<n;i++)
    col[i]=F(),la[col[i]]!=-1?R[la[col[i]]]=i:1,
    L[i]=pre[i]=la[col[i]],la[col[i]]=i;
    for(l=0,r=m-1;l<=n;l+=m,r+=m)std::sort(pre+l,r<n-1?pre+r+1:pre+n);
    for(;K--;){
        while(op=getchar(),op!='Q'&&op!='R');l=F()-1,r=F(),ans=0;
        if(op=='Q'){
            if(--r,l/m==r/m)vio(l,r);
            else{
                vio(l,j=l/m*m+m-1);
                vio(k=r/m*m,r);
                for(r=k-1,j++,k=j+m-1;k<=r;j+=m,k+=m)bin(j,k,l);
            }
            printf("%d\n",ans);
        }
        else{
            i=L[l],j=R[l];
            if(i!=-1)R[i]=j;
            if(j!=-1)L[j]=i;
            t[0]=l/m;t[1]=(j!=-1?j:l)/m;
            for(i=l-1;~i&&col[i]!=r;i--);
            for(j=l+1;j<n&&col[j]!=r;j++);
            t[2]=(j<n?j:l)/m;std::sort(t,t+3);
            L[l]=i;if(i!=-1)R[i]=l;
            if(j<n)R[l]=j,L[j]=l;else R[l]=-1;
            if(t[0]!=t[1])update(t[0]);
            if(t[1]!=t[2])update(t[1]);
            update(t[2]);col[l]=r;
        }
    }
}
  评论这张
 
阅读(62)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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