hash树三题

发表于 2017-03-22   |   分类于 hash , 线段树  |  访问: 48 次

-->题目链接<--

第一题蛮重要,毕竟感觉学了新知识

惭愧,自上次考完已三个月多没更新博客,也迷茫了一段时间

这题是一题线段树,乍一看怎么也看不出线段树对吧

暴力的做法不谈,在这可获得30分

我们来看看优美的正解

[弱弱的看了两天代码学习了线段树hash]

可以发现每个数字只出现一次

所以当某个数字x出现了

那么x-d也出现,但x+d未出现时

必定存在一个长度为3的等差序列

所以确实容易发现找到一个长度为3的等差序列即可

关键是如何优化查找的过程呢

有篇论文是06年一个神犇写的

就是讲了hash的优美

建议先去找找那篇论文

言归正传,怎么知道x-d出现而x+d有没有出现呢

首先是3,所以把b[3]=1

此时发现b[3]左边为00

右边为00

这里所说的相等指的是左右两边接起来可以变成回文串

左边=右边

所以不存在有一个值d(d可为负,不影响)使得

3-d出现而3+d没有出现

继续把b[5]=1

b[5]右边不存在值

所以左边连看都不用看

因为肯定不存在5-d出现而5+d没有出现

接着是b[2]=1

由于b[2]左边只有一格

所以右边也只要取一格

左边=0

右边=1

因为左边!=右边

所以此时存在一个d=-1

使得2-d=3出现

但2+d=1未出现

则a这个序列必定存在等差子序列

知道如何确定答案这个过程以后

就需要想想怎么维护了

这里用的是hash,并且用的是线段树hash

可以实现每次查询logn次获取左右两边的hash值并且进行比较

因为正向需要维护,逆向也需要维护

故需要两棵线段树

【其实开个二维数组写一起就行了】

维护过程较为玄学【只是不想画图罢了】

所以建议看代码自行模拟【跑路】

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int modd=100000007;
const int _maxn=10010;
ll p[_maxn],tree[_maxn<<2][2];
void update(int pos,int l,int r,int x){
	if(l==r)
		tree[pos][0]=tree[pos][1]=1;
	else{
		int mid=(l+r)>>1;
		if(x<=mid)	update(pos<<1,l,mid,x);
		else		update(pos<<1|1,mid+1,r,x);
		tree[pos][0]=(tree[pos<<1|1][0]+tree[pos<<1][0]*p[r-((r+l)>>1)]%modd)%modd;
		tree[pos][1]=(tree[pos<<1][1]+tree[pos<<1|1][1]*p[((r+l)>>1)-l+1]%modd)%modd;
	}
}
ll query(int pos,int l,int r,int y1,int y2,int flag){
	if(l==y1 && r==y2)	return tree[pos][flag];
	int mid=(l+r)>>1;
	ll left=0,right=0;
	if(mid<y2)	right=query(pos<<1|1,mid+1,r,max(y1,mid+1),y2,flag);
	if(mid>=y1)	left=query(pos<<1,l,mid,y1,min(y2,mid),flag);
	return (flag?left+right*p[max(0,mid-y1+1)]%modd:right+left*p[max(0,y2-mid)]%modd)%modd;
}
int main(){
	int t,x,n,len;
	bool flag;
	scanf("%d",&t);
	p[0]=1;
	for(int i=1;i<10001;i++)
		p[i]=(p[i-1]<<1)%modd;
	while(t--){
		flag=true;
		int i;
		scanf("%d",&n);
		memset(tree,0,sizeof(tree));
		for(i=1;i<=n;i++){
			scanf("%d",&x);
			len=min(x-1,n-x);
			int temp1,temp2;
			if(len){
				temp1=query(1,1,n,x-len,x-1,0);
				temp2=query(1,1,n,x+1,x+len,1);
			}
			if(flag && len && temp1!=temp2){
				printf("Y\n");
				flag=false;
			}
			update(1,1,n,x);
		}
		if(flag)
			printf("N\n");
	}
	return 0;
}

等真正模拟出来就能体会到hash的优美了

【自己太ruo花了一节课才模拟出来】


-->第二题是ural1989<--

题目大意是给定一个字符串

一些操作

1.查询[l,r]是不是回文串

2.把a[x]修改成给定的字符

其实如果第一题能理解

那么这题的意思是差不多的嘛

就是建立正反两棵hash树状数组

然后进行查询和单点修改

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
const int _maxn=100005;
char a[_maxn],s[20];
int n;
ll tree[_maxn][2],pow[_maxn];
int lowbit(int x){return x&(-x);}
void add(int x,ll d,int y){
	while(x<=n){
		tree[x][y]+=d;
		x+=lowbit(x);
	}
}
ll sum(int x,int y){
	ll ans=0;
	while(x>0){
		ans+=tree[x][y];
		x-=lowbit(x);
	}
	return ans;
}
int main(){
	pow[0]=1;
	int m,y1,y2;
	ll left,right;
	for(int i=1;i<=100000;i++)
		pow[i]=pow[i-1]*27;
	while(scanf("%s",a+1)!=EOF){
		memset(tree,0,sizeof(tree));
		n=strlen(a+1);
		for(int i=1;i<=n;i++){
			add(i,(a[i]-'a')*pow[i-1],0);
			add(i,(a[n-i+1]-'a')*pow[i-1],1);
		}
		scanf("%d",&m);
		while(m--){
			scanf("%s",s);
			if(s[0]=='p'){
				scanf("%d%d",&y1,&y2);
				left=(sum(y2,0)-sum(y1-1,0))*pow[n-y2];
				right=(sum(n-y1+1,1)-sum(n-y2,1))*pow[y1-1];
				if(left==right)	printf("Yes\n");
				else			printf("No\n");
			}
			else{
				scanf("%d%s",&y1,s);
				y2=s[0]-a[y1];
				add(y1,y2*pow[y1-1],0);
				add(n-y1+1,y2*pow[n-y1],1);
				a[y1]=s[0];
			}
		}
	}
	return 0;
}

 


-->第三题类似的<--

题目大意给定一些字符串s[i]

在另一串里的[l,r]是否有在s中出现过的串

多组数据

注意空间大小

持续RE然后卡成WA

。。。。心累

实际上我是先计算s[i]的hash值并且开个bool存起来

接着我们计算另一串里的[l,r]的hash值

然后O(1)查询一下就可以啦

当然有人用map<long long,bool>也行

还看到有更牛逼的强行模拟

orz,反正我是想不出来

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int _maxn=400010,modd=5008387;
typedef long long ll;
int t,n,m;
ll tree[_maxn<<2],pow[_maxn];
bool vis[modd];
char s[_maxn*20];
void calc(){
	int len=strlen(s);
	ll ans=0;
	for(int i=0;i<len;i++)
		ans=(ans+(s[i]-'a'+1)*pow[i]%modd)%modd;
	vis[(int)ans]=true;
}
void push(int pos,int l,int r,int x,int keynum){
	if(l==r){	tree[pos]=keynum;	return;}
	int mid=(l+r)>>1;
	if(mid>=x)	push(pos<<1,l,mid,x,keynum);
	else		push(pos<<1|1,mid+1,r,x,keynum);
	tree[pos]=(tree[pos<<1]+tree[pos<<1|1]*pow[mid-l+1]%modd)%modd;
}
int query(int pos,int l,int r,int y1,int y2){
	if(y1==l && y2==r)	return tree[pos];
	int mid=(l+r)>>1;
	ll left=0,right=0;
	if(mid>=y1)	left=query(pos<<1,l,mid,y1,min(y2,mid));
	if(mid<y2)	right=query(pos<<1|1,mid+1,r,max(y1,mid+1),y2);
	return (left+right*pow[max(0,mid-y1+1)]%modd)%modd;
}
int main(){
	freopen("in.in","r",stdin);
	scanf("%d",&t);
	int p,y1,y2,ca=0;
	pow[0]=1;
	for(int i=1;i<100001;i++)
		pow[i]=(pow[i-1]*29)%modd;
	while(t--){
		printf("Case #%d:\n",++ca);
		memset(tree,0,sizeof(tree));
		memset(vis,false,sizeof(vis));
		scanf("%d",&p);
		for(int i=1;i<=p;i++){
			scanf("%s",s);
			calc();
		}
		scanf("%s",s);
		n=strlen(s);
		for(int i=0;i<n;i++)
			push(1,1,n,i+1,s[i]-'a'+1);
		scanf("%d",&m);
		for(int i=1;i<=m;i++){
			scanf("%s",s);
			if(s[0]=='Q'){
				scanf("%d%d",&y1,&y2);
				if(vis[(int)query(1,1,n,y1+1,y2+1)])
					printf("Yes\n");
				else	printf("No\n");
			}
			else{
				scanf("%d%s",&y1,s);
				push(1,1,n,y1+1,s[0]-'a'+1);
			}
		}
	}
	return 0;
}

 

发表新评论

© 2017 Powered by Typecho & Theme Quark