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

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

CF144 DIV1 完挂 (含后缀数组)  

2012-10-12 01:44:19|  分类: CodeForces |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
还未考完就宣布了我的失利
被hack了,还要说什么呢?
取模时除了问题,我竟然会犯这种错误,真的看不到什么前途了
本还指望靠这次+rating的,看来必定会掉了
最可恨的不是我的失误,而是我没等考完就颓废去了,导致被hack时未及时发现
愧疚啊!一定要认真对待每一个程序,因为,再简单的题也会把我坑到。

好吧,昨天经过努力总算把题目改完了,感触万分啊
可恨的C,竟然卡常数,卡得我要死要活的
不想说什么了

D倒是蛮不错的题目,后缀数组+主席树直接秒,虽说写了整整一上午,唉,毕竟还是不熟啊!

E想起来很难,但写起来却是蛮容易的,分治的思想很巧妙,利用位运算从根本上降低常数。
只可惜明明是陈丹琦分治的思想,为何就偏偏没想到这方面呢?
太弱了太弱了。

贴上D的代码,作为后缀数组的模板

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;

const int MAX=1000000+10;
const int INF=2000000000;
const int NUM=21;

int n,H[MAX],d[MAX],m,Q;

struct Li
{
int i,num;
Li(){}
Li(int a,int b){i=a;num=b;}
}L[MAX];
int numL;

int cmp(const Li& a,const Li& b)
{
return a.num<b.num;
}

int rank[MAX],w[MAX],v[MAX],sa[MAX],y[MAX],height[MAX],h[MAX];
int st[MAX][20],mm[MAX];

int compare(int a,int b,int len)
{
if(v[a]!=v[b])return v[a]!=v[b];
return v[a+len]<v[b+len];
}

void suffix_array(int* d,int n,int m,int *rank,int *sa)
{
int i,j,top=0,len,p=m;
for(i=1;i<=n;++i)w[i]=0,rank[i]=d[i];
for(i=1;i<=n;++i)++w[d[i]];
for(i=1;i<=m;++i)w[i]+=w[i-1];
for(i=n;i>=1;--i)sa[w[d[i]]--]=i;
for(j=1;(1<<(j-1))<n;++j)
{
top=0,len=(1<<(j-1));
for(i=1;i<=n;++i)if(sa[i]>n-len)y[++top]=sa[i];
for(i=1;i<=n;++i)if(sa[i]>len)y[++top]=sa[i]-len;
for(i=1;i<=p;++i)w[i]=0;
for(i=1;i<=n;++i)v[i]=rank[i];
for(i=1;i<=n;++i)++w[v[i]];
for(i=1;i<=p;++i)w[i]+=w[i-1];
for(i=n;i>=1;--i)sa[w[v[ y[i] ]]--]=y[i];
p=0;
for(i=1;i<=n;++i)
{
if(i==1 || compare(sa[i-1],sa[i],len))++p;
rank[sa[i]]=p;
}
}
}

void calHeight(int* sa,int* rank,int* h,int* height,int* d,int n)
{
int x=0,j,i;
h[0]=0;
for(i=1;i<=n;++i)
{
x=max(h[i-1]-1,0),j=sa[rank[i]-1];
for(;i+x<=n && j+x<=n && d[i+x]==d[j+x];++x);
h[i]=x;
}
for(i=1;i<=n;++i)
height[i]=h[sa[i]];
}

void initRMQ(int* height,int n)
{
int i,j;
mm[1]=0;
for(i=2;i<MAX;++i)
{
mm[i]=mm[i-1];
if((i&(i-1))==0)++mm[i];
}
for(i=1;i<=n;++i)
st[i][0]=height[i];
for(j=1;(1<<j)<=n;++j)
for(i=1;i<=n;++i)
{
st[i][j]=st[i][j-1];
if(i+(1<<(j-1))<=n)
st[i][j]=min(st[i][j],st[i+(1<<(j-1))][j-1]);
}
}

int askRMQ(int a,int b)
{
if(a>b)swap(a,b);
int k=(b-a+1);
k=mm[k];
b=b-(1<<k)+1;
return min(st[a][k],st[b][k]);
}

struct node
{
int lc,rc,sum;
node(){lc=rc=sum=0;}
}tree[MAX*4];
int node,root[MAX*4],cnt;

void revice(int u,int now,int l,int r,int x)
{
tree[u]=tree[now];
++tree[u].sum;
if(l==r)return;
int mid=(l+r)/2;
if(x<=mid)
{
tree[u].lc=++cnt;
revice(tree[u].lc,tree[now].lc,l,mid,x);
}
else
{
tree[u].rc=++cnt;
revice(tree[u].rc,tree[now].rc,mid+1,r,x);
}
}

int ask(int u,int l,int r,int a,int b)
{
if(r<a || l>b)return 0;
if(a<=l && r<=b)return tree[u].sum;
int mid=(l+r)/2;
return ask(tree[u].lc,l,mid,a,b)+ask(tree[u].rc,mid+1,r,a,b);
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#endif
int i,x,y,a,b;
scanf("%d",&n);
for(i=1;i<=n;++i)
scanf("%d",&H[i]);
for(i=1;i<=n-1;++i)d[i]=H[i]-H[i+1];
d[n]=-INF;
for(i=n+1;i<=n+(n-1);++i)
d[i]=H[i-n+1]-H[i-n];
d[2*n]=-INF-1;
for(i=1;i<=2*n;++i)
L[++numL]=Li(i,d[i]);
sort(L+1,L+numL+1,cmp);
for(m=0,i=1;i<=2*n;++i)
{
if(i==1 || L[i].num!=L[i-1].num)++m;
d[L[i].i]=m;
}
suffix_array(d,2*n,m,rank,sa);
calHeight(sa,rank,h,height,d,2*n);
initRMQ(height,2*n);
for(i=1;i<=2*n;++i)
{
root[i]=++cnt;
revice(root[i],root[i-1],1,2*n,sa[i]);
}
scanf("%d",&Q);
int left,right=0,mid,len,ans=0,l,r;
for(i=1;i<=Q;++i)
{
ans=0;
scanf("%d %d",&x,&y);
if(x==y)
{
printf("%d\n",n-1);
continue;
}
--y;
len=y-x+1;

if(rank[x]!=1)
{
left=2,right=rank[x];
while(left<right)
{
mid=(left+right)/2;
if(askRMQ(mid,rank[x])>=len)right=mid;
else left=mid+1;
}
if(askRMQ(left,rank[x])>=len)l=left-1;
else l=rank[x];
}
else l=rank[x];

if(rank[x]!=2*n)
{
left=rank[x]+1,right=2*n;
while(left<right)
{
mid=(left+right+1)/2;
if(askRMQ(mid,rank[x]+1)>=len)left=mid;
else right=mid-1;
}
if(askRMQ(left,rank[x]+1)>=len)r=left;
else r=rank[x];
}
else r=rank[x];

a=n+1,b=n+x-len-1;
if(a<=b)ans+=ask(root[r],1,2*n,a,b)-ask(root[l-1],1,2*n,a,b);
a=n+y+2,b=2*n;
if(a<=b)ans+=ask(root[r],1,2*n,a,b)-ask(root[l-1],1,2*n,a,b);
printf("%d\n",ans);
}
return 0;
}



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

历史上的今天

评论

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

页脚

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