首页 > 代码库 > HDU 4339 线段树区间合并

HDU 4339 线段树区间合并

2024-07-14 03:13:29   230人阅读

Query

Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2573    Accepted Submission(s): 851


Problem Description
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].
 

 

Input
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.
 

 

Output
For each test output "Case t:" in a single line, where t is number of test (numbered from 1 to T).
Then for each query "2 i" output in single line one integer j.
 

 

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

 

Sample Output
Case 1:
2
1
0
1
4
1
 
 
 
 
题目意思：
给两个字符串s1, s2， 然后m组操作，共有两种操作1和2，  若为1，输入a, i, c即把第a个字符串（a==1||a==2）的第 i 个位置处的字符用 c 替换；若为2，输入x，即s1,s2都从x开始匹配最远到第j处位置，输出j。
 
思路：
把两个字符串比较相同的元素为1否则为0放在一个数组p[]中，然后把p[]挂在线段树叶子节点处，然后往上更新。
线段树节点包含这么几个元素：l, r(左边界、右边界), lm, rm(从左边界开始1的最长连续段的长度，以右边界为止1的最长连续段的长度)， mm(线段中1的最长的连续段长度)。（区间合并的老套路。。。）
其他的基本上就是老套路了，主要注意一下求和输出，还是直接看代码比较容易上手：
 
  1 #include <cstdio>  2 #include <cstring>  3 #include <algorithm>  4 #include <iostream>  5 using namespace std;  6 #define N 1000005  7 #define ll root<<1  8 #define rr root<<1|1  9 #define mid (a[root].l+a[root].r)/2 10  11 int p[1000005]; 12 char s1[1000005]; 13 char s2[1000005]; 14  15 struct node{ 16     int l, r; 17     int lm, rm, mm; 18 }a[4*N]; 19  20  21 void up(int root){                        //貌似线段树区间合并都有这个函数  22     if(a[root].l==a[root].r) return; 23     a[root].lm=a[ll].lm; 24     a[root].rm=a[rr].rm; 25     a[root].mm=max(a[ll].mm,a[rr].mm); 26     if(a[ll].lm==a[ll].r-a[ll].l+1) a[root].lm+=a[rr].lm; 27     if(a[rr].rm==a[rr].r-a[rr].l+1) a[root].rm+=a[ll].rm; 28     a[root].mm=max(max(a[root].lm,a[root].rm),max(a[root].mm,a[ll].rm+a[rr].lm)); 29 } 30  31 void build(int l,int r,int root){ 32     a[root].l=l; 33     a[root].r=r; 34     if(l==r){ 35         a[root].lm=a[root].rm=a[root].mm=p[l]; 36         return; 37     } 38     build(l,mid,ll); 39     build(mid+1,r,rr); 40     up(root); 41 } 42  43 void update(int q,int val,int root){ 44     if(a[root].l==q&&a[root].r==q){ 45         a[root].lm=a[root].mm=a[root].rm=val; 46         return; 47     } 48     if(q<=mid) update(q,val,ll); 49     else update(q,val,rr); 50     up(root); 51 } 52  53 int query(int q,int root){ 54     if(a[root].l==a[root].r){ 55         return a[root].mm; 56     } 57     if(q<=mid){ 58         if(q>=a[ll].r-a[ll].rm+1) return a[ll].r-q+1+query(mid+1,rr);        //若q在左子树且在左子树1右连续段则需要加上右子树1左连续段  59         else return query(q,ll);                          60     } 61     else{ 62         return query(q,rr); 63     } 64 } 65  66 main() 67 { 68     int t, kase=1; 69     int i, j, k, m; 70     int n1, n2; 71     int x, y, z; 72     char c[5]; 73     scanf("%d",&t); 74     while(t--){ 75         //memset(p,0,sizeof(p)); 76         printf("Case %d:\n",kase++); 77         scanf("%s%s",s1,s2); 78         n1=strlen(s1); 79         n2=strlen(s2); 80         for(i=0;i<min(n1,n2);i++){ 81             if(s1[i]==s2[i]) p[i]=1;                  //相同为1否则为0  82             else p[i]=0; 83         } 84         for(i=min(n1,n2);i<max(n1,n2);i++){ 85             p[i]=0; 86         } 87         build(0,max(n1,n2)-1,1); 88         scanf("%d",&m); 89         while(m--){ 90             scanf("%d",&z); 91             if(z==1){ 92                 scanf("%d %d %s",&x,&y,c); 93                 if(x==1){ 94                     s1[y]=c[0]; 95                 } 96                 else s2[y]=c[0]; 97                 p[y]=(s1[y]==s2[y]?1:0); 98                 update(y,p[y],1); 99             }100             else{101                 scanf("%d",&x);102                 printf("%d\n",query(x,1));103             }104         }105     }106 }

 


联系
我们