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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ3585]mex  

2014-10-16 11:27:33|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3585: mex

看大家都做了于是就去做了
结果用了奇怪的方法导致超级慢……
全BZOJ最后一名QAQ(也算是个成就了
最后加了个几乎没用的优化又加了个读入挂总算变成倒数第二了TuT
话说我Blog新换的主题怎么样,个人感觉比原来看得清楚了。。
题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int N = 2e5+10;
const int N2 = N*2;
int n,m,data[N],ans[N],num[N];
int lson[N2],rson[N2],tree[N2],T,ROOT,tn;
//int scan(){int i=0;scanf("%d",&i);return i;}
int scan(){
char cc=' ';int re=0,fh=1;
while(cc==' '||cc=='\r'||cc=='\n')cc=getchar();
if(cc=='+')cc=getchar(),fh=1;
if(cc=='-')cc=getchar(),fh=-1;
while('0'<=cc&&cc<='9'){
re=re*10+cc-'0';
cc=getchar();
}
return re*fh;
}
struct ASK{
int l,r,i;
ASK(){}
ASK(int ll,int rr,int ii):l(ll),r(rr),i(ii){}
}ask[N];
int Build(int l=1,int r=tn){
int re = ++T;
if(l<r){
int mid = (l+r)/2;
lson[re] = Build(l,mid);
rson[re] = Build(mid+1,r);
}
return re;
}
void set(int x,int val){
int ro = ROOT,l = 1,r = tn;
tree[ro]+=val;
while(l<r){
int mid = (l+r)/2;
if(x<=mid) ro = lson[ro],r = mid;
else ro = rson[ro],l = mid+1;
tree[ro]+=val;
}
}
int query(){
int ro = ROOT,l = 1,r = tn;
while(l<r){
int mid = (l+r)/2;
if((mid - l + 1) > tree[lson[ro]])ro = lson[ro],r = mid;
else ro = rson[ro],l = mid+1;
}return l;
}
int kuai[N];
bool cmp(ASK a,ASK b){
if(kuai[a.l] == kuai[b.l]) return a.r < b.r;
return kuai[a.l] < kuai[b.l];
}
void change(int x,short t){
if(x > n)return;
if(t > 0){
if(!num[x]) set(x,1);
num[x]++;
}else{
num[x]--;
if(!num[x]) set(x,-1);
}
}
int main(){
int i,j,a,b,sqn,l,r;
n = scan();m = scan();
sqn = sqrt(n);
for(i=1;i<=n;i++)data[i] = scan()+1;
for(i=1;i<=n;i++)kuai[i] = i/sqn;
for(i=1;i<=m;i++){
a = scan();b = scan();
ask[i] = ASK(a,b,i);
}
tn = n+1;
ROOT = Build();
sort(ask+1,ask+1+m,cmp);
l = 1;r = 0;
for(i=1;i<=m;i++){
while(l < ask[i].l && l<=r) change(data[l],-1),l++;
if(l>r)l = ask[i].l,r = l-1;
while(r < ask[i].r) r++,change(data[r],1);
while(r > ask[i].r && l<=r) change(data[r],-1),r--;
if(l>r)r = ask[i].r,l = r+1;
while(l > ask[i].l) l--,change(data[l],1);
ans[ask[i].i] = query();
}
for(i=1;i<=m;i++)
printf("%d\n",ans[i]-1);
return 0;
}

题解:
好孩子不要学我的做法自己去网上找标解
莫队+线段树 总时间复杂度O(n^1.5 * logn) (没T真是个奇迹
感觉是非常显而易见的做法,用线段树维护一个数组,表示值为i的数是否出现过,出现过就是1
然后查询的时候就在树上二分答案就好了
正解等我有空的时候再研究>A<
Update: 2014-11-21 19:56:27
转了好几个地方才看懂,果然是我语文水平太差了么
至于在线做法,2L主席的说法是不可行的,但是2L回复里给出了另一种比较蛋疼的方法:对于离线的线段树直接进行可持久化。感觉写起来会蛋疼啊……
  评论这张
 
阅读(41)| 评论(6)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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