首页 > ACM题库 > HDU-杭电 > HDU 4339-Query-线段树-[解题报告]HOJ
2015
05-23

HDU 4339-Query-线段树-[解题报告]HOJ

Query

问题描述 :

You are given two strings s1[0..l1], s2[0..l2] and Q – number of queries.
Your task is to answer next queries:
  1) 1 a i c – you should set i-th character in a-th string to c;
  2) 2 i – you should output the greatest j such that for all k (i<=k and k<i+j) s1[k] equals s2[k].

输入:

The first line contains T – number of test cases (T<=25).
Next T blocks contain each test.
The first line of test contains s1.
The second line of test contains s2.
The third line of test contains Q.
Next Q lines of test contain each query:
  1) 1 a i c (a is 1 or 2, 0<=i, i<length of a-th string, ‘a’<=c, c<=’z')
  2) 2 i (0<=i, i<l1, i<l2)
All characters in strings are from ‘a’..’z’ (lowercase latin letters).
Q <= 100000.
l1, l2 <= 1000000.

输出:

The first line contains T – number of test cases (T<=25).
Next T blocks contain each test.
The first line of test contains s1.
The second line of test contains s2.
The third line of test contains Q.
Next Q lines of test contain each query:
  1) 1 a i c (a is 1 or 2, 0<=i, i<length of a-th string, ‘a’<=c, c<=’z')
  2) 2 i (0<=i, i<l1, i<l2)
All characters in strings are from ‘a’..’z’ (lowercase latin letters).
Q <= 100000.
l1, l2 <= 1000000.

样例输入:

1
aaabba
aabbaa
7
2 0
2 1
2 2
2 3
1 1 2 b
2 0
2 3

样例输出:

Case 1:
2
1
0
1
4
1

/*
分析:
    线段树水题。
    被小坑了一下、没有说两个串长度一样呢囧~。不过好久没
敲过线段树了、还是蛮happy滴~^_^
    我维护的是:该区间内、从左端点开始往右能在对应相等的
前提下所延伸的最长长度。

                                          2013-07-17
*/

#include"iostream"
#include"cstdio"
#include"cstring"
using namespace std;
const int N=1000010;

int ltr[N<<2];
char s[2][N];

void build(int l,int r,int k)
{
	if(l==r)
	{
		if(s[0][l]==s[1][l])	ltr[k]=1;
		else	ltr[k]=0;
		return ;
	}
	int mid=(l+r)>>1;
	int l_son=k<<1;
	int r_son=l_son+1;
	build(l,mid,l_son);
	build(mid+1,r,r_son);
	ltr[k]=ltr[l_son];
	if(ltr[l_son]==mid-l+1)	ltr[k]+=ltr[r_son];
}
void update(int l,int r,int z,int aim,char c,int k)
{
	if(l==r)
	{
		s[z][aim]=c;
		ltr[k]=s[0][aim]==s[1][aim];
		return ;
	}
	int mid=(l+r)>>1;
	int l_son=k<<1;
	int r_son=l_son+1;
	if(aim<=mid)update(l,mid,z,aim,c,l_son);
	else		update(mid+1,r,z,aim,c,r_son);
	ltr[k]=ltr[l_son];
	if(ltr[l_son]==mid-l+1)	ltr[k]+=ltr[r_son];
}
int find(int l,int r,int aim,int k)
{
	if(l==aim)	return ltr[k];

	int mid=(l+r)>>1;
	int l_son=k<<1;
	int r_son=l_son+1;
	int ans;
	if(aim<=mid)
	{
		ans=find(l,mid,aim,l_son);
		if(ans==mid-aim+1)	ans+=find(mid+1,r,mid+1,r_son);
	}
	else	ans=find(mid+1,r,aim,r_son);
	return ans;
}
int main()
{
	int T,Case;
	int i;
	int len,q;
	int x,a,b;
	char c[10];
	cin>>T;
	for(Case=1;Case<=T;Case++)
	{
		scanf("%s%s",s[0]+1,s[1]+1);
		i=1;
		while(s[0][i] && s[1][i])	i++;
		len=i-1;
		i=1;
		build(1,len,1);

		cin>>q;
		printf("Case %d:\n",Case);
		while(q--)
		{
			scanf("%d",&x);
			if(x==1)
			{
				scanf("%d%d%s",&a,&b,c);
				if(b+1>len)	continue;
				update(1,len,a-1,b+1,c[0],1);
			}
			else
			{
				scanf("%d",&b);
				if(b+1>len)	printf("0\n");
				else		printf("%d\n",find(1,len,b+1,1));
			}
		}
	}
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/ice_crazy/article/details/9359787