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

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

CF 131 div1 E treap+hash  

2012-10-10 10:24:22|  分类: CodeForces |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
题解中用线段树的做法一直没看懂
于是yy了一个用treap+hash的做法

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

typedef long long LL;
const int MAX=200000+1000;
const int INF=1000000000;
const int Delta=200000;
const LL Mod=1000000007;
const LL MULT=1000003;

int n,m,a[MAX],b[MAX],pb[MAX];
LL pow[MAX];

struct Node
{
int size,v,w,ch[2],p;
LL hash,val;
Node()
{
size=v=w=ch[0]=ch[1]=p=hash=0;
}
}tree[MAX];
int Root;

void update(int u)
{
LL l=tree[tree[u].ch[0]].hash;
LL r=tree[tree[u].ch[1]].hash;
LL mid=tree[u].val;
int s=tree[tree[u].ch[1]].size;
tree[u].hash=(l*pow[s+1]+mid*pow[s]+r)%Mod;
tree[u].size=tree[tree[u].ch[0]].size+tree[tree[u].ch[1]].size+1;
}

void rotate(int u)
{
int fa=tree[u].p,gfa=tree[fa].p;
int T=(tree[fa].ch[1]==u),H=T^1;
tree[fa].ch[T]=tree[u].ch[H];tree[tree[u].ch[H]].p=fa;
tree[fa].p=u;tree[u].ch[H]=fa;
if(tree[gfa].ch[1]==fa)tree[gfa].ch[1]=u;
else tree[gfa].ch[0]=u;
tree[u].p=gfa;
if(!gfa)Root=u;
update(fa);update(u);
}

void down(int u)
{
int m=u;
if(tree[u].ch[0] && tree[tree[u].ch[0]].w<tree[m].w)
m=tree[u].ch[0];
if(tree[u].ch[1] && tree[tree[u].ch[1]].w<tree[m].w)
m=tree[u].ch[1];
if(m!=u)rotate(m),down(u);
}

void up(int u)
{
while(tree[u].p && tree[u].w<tree[tree[u].p].w)
rotate(u);
}

void update_path(int u)
{
for(;u;u=tree[u].p)update(u);
}

void insert(int u)
{
tree[u].w=rand()%1000000;
tree[u].size=1;
if(!Root)
{
Root=u;
return;
}
int now=Root,T;
while(1)
{
T=tree[u].v>tree[now].v;
if(tree[now].ch[T])now=tree[now].ch[T];
else break;
}
tree[u].p=now;tree[now].ch[T]=u;
update_path(u);
up(u);
return;
}

void del(int u)
{
tree[u].w=INF;
down(u);
if(!tree[u].p){Root=0;return;}
int fa=tree[u].p;
int T=(tree[fa].ch[1]==u);
tree[fa].ch[T]=0;tree[u].p=0;
update_path(fa);update(u);
}

int findsmall(int now,int w)
{
if(!now)return 0;
int t;
if(tree[now].v<w)
{
if( ( t=findsmall(tree[now].ch[1],w) ) )return t;
return now;
}
else return findsmall(tree[now].ch[0],w);
}

int findbiger(int now,int w)
{
if(!now)return 0;
int t;
if(tree[now].v>w)
{
if( ( t=findbiger(tree[now].ch[0],w) ) )return t;
else return now;
}
else return findbiger(tree[now].ch[1],w);
}

void Del(int u)
{
del(u);
int less=findsmall(Root,tree[u].v);
int more=findbiger(Root,tree[u].v);
if(!more)
return;
if(less)
tree[more].val=more-less+Delta;
else
tree[more].val=0;
update_path(more);
}

void Ins(int u)
{
tree[u].v=pb[u];
int less=findsmall(Root,tree[u].v);
int more=findbiger(Root,tree[u].v);

if(less)tree[u].hash=tree[u].val=u-less+Delta;
else tree[u].hash=tree[u].val=0;
if(more)
{
tree[more].val=more-u+Delta;
update_path(more);
}
insert(u);
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#endif
srand(1234);
scanf("%d %d",&n,&m);
int i;
for(i=1;i<=n;++i)
scanf("%d",&a[i]);
for(i=1;i<=m;++i)
{
scanf("%d",&b[i]);
pb[b[i]]=i;
}
pow[0]=1;
for(i=1;i<MAX;++i)
pow[i]=pow[i-1]*MULT%Mod;
LL aim=0;
for(i=2;i<=n;++i)
aim=(aim*MULT+a[i]-a[i-1]+Delta)%Mod;
int ans=0;
for(i=1;i<=m;++i)
{
Ins(i);
if(i>n)Del(i-n);
if(i>=n)if(tree[Root].hash==aim)++ans;
}
printf("%d\n",ans);
}




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

历史上的今天

评论

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

页脚

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