HDU 4339 Query

算法:

比賽時沒有想到好的算法，暴力是O（ Q * N ）肯定超時。

賽后，線段樹，樹狀數組，HASH都能AC，想了下，的確用樹狀數組

時間復雜度就可以優化到O（Q * lgN * lgN)

2000msAC.。。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<vector>
#include<string>
#include<math.h>
#include<map>
#include<set>
#include<algorithm>
using namespace std;
#define MAXN 2000100
char str1[MAXN],str2[MAXN],str[10];
int  dx[MAXN];
int N, lenmax, lenmin;int lowbit( int x )
{    return x&-x;   
}void add( int x, int val, int M)
{while( x <= M ){dx[x] += val;x += lowbit(x);}     }int sum( int x )
{int num = 0;while( x > 0 ){num += dx[x];x -= lowbit( x );      }   return num;  
}void pre( )
{int i = 1;int len1 = strlen(str1+1), len2 = strlen(str2+1);lenmin = len1 < len2 ? len1 : len2;while( i <= len1 ){if( str1[i] == str2[i] ){add(i, 1, lenmin);   }     i++;       }          
}bool jugde(int start, int x)
{int x1 = sum(start+x-1) - sum(start-1);if( x1 == x )return true;return false;
}int find( int l, int r, int start)
{int ans = 0;while( l <= r ){int mid = (l + r)/2;if( jugde(start,mid) ){ans = mid;l = mid + 1;    }else r = mid - 1; }return ans;  
}int main( )
{int T, a, b, c, ans = 1;scanf("%d",&T);while( T-- ){scanf("%s%s",str1+1,str2+1);      scanf("%d",&N);memset(dx,0,sizeof(dx));pre( );printf("Case %d:\n",ans++);for( int i = 1; i <= N; i++){scanf("%d",&a);if( a == 2 ){scanf("%d",&b);b++;printf("%d\n",find(0,lenmin,b));}else{ scanf("%d%d%s",&b,&c,str);c++;  if( str1[c] == str2[c] && str[0] != str1[c] ){add(c,-1,lenmin);if( b == 1 )str1[c] = str[0];elsestr2[c] = str[0];}else if( str1[c] != str2[c] ){if( b == 1 ){if( str2[c] == str[0] ){add(c,1,lenmin);   str1[c] = str[0];     }elsestr1[c] = str[0];    }else if( b == 2 ){if( str1[c] == str[0] ){add(c,1,lenmin);   str2[c] = str[0];     }     elsestr2[c] = str[0];  }     } }}     }return 0;
}

HASH，要用到差值取模，時間復雜度為O（ Q * lgN），寫了一兩個小時，還在調試中。。代碼能力弱啊。。。

明天繼續搞。。

郁悶啊。。從下到上的最大長度寫了N久沒寫出，自己感覺真的不好寫，從上到下真的很好寫,利用回溯，寫起來真的方便，自己。。

一直被標程的從下到上困擾，真的二，忘記了還可以從上到下。thanks 旭。。

#pragma comment(linker, "/STACK:16777216")
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<vector>
#include<string>
#include<math.h>
#include<map>
#include<set>
#include<algorithm>
using namespace std;
#define MAXN 1000010
#define Prime 29
#define LL long long
struct node
{int left, right;LL w1,w2;
}seg[MAXN<<4];
char str1[MAXN], str2[MAXN], str[10];
LL P[MAXN];
int num[MAXN], nmax;void pre( )
{P[0] = 1;for( int i = 1;  i <= 1000005; i++)P[i] = P[i-1] * Prime;     }void build( int l, int r, int root )
{int mid = (l + r) / 2;seg[root].left = l;seg[root].right = r;if( l == r ){seg[root].w1 = str1[l];seg[root].w2 = str2[l];num[l] = root;return;  }build(l, mid, root * 2 );build(mid+1,r,root * 2 + 1);seg[root].w1 = seg[root << 1].w1 + seg[(root<<1)+1].w1 * P[( seg[root<<1].right - seg[root<<1].left + 1)];seg[root].w2 = seg[root << 1].w2 + seg[(root<<1)+1].w2 * P[( seg[root<<1].right - seg[root<<1].left + 1)];
}void Modify( int root, int x, char c, int f)
{int mid = (seg[root].left + seg[root].right) / 2;int l = seg[root].left;int r = seg[root].right;if( l == x && r == x ){if( f == 1 )seg[root].w1 = c ;elseseg[root].w2 = c ;return;}if( x > mid )Modify( (root << 1) + 1, x, c, f);elseModify( root << 1, x, c, f);if( f == 1 )seg[root].w1 = seg[root << 1].w1 + seg[(root<<1)+1].w1 * P[( seg[root<<1].right - seg[root<<1].left + 1)];elseseg[root].w2 = seg[root << 1].w2 + seg[(root<<1)+1].w2 * P[( seg[root<<1].right - seg[root<<1].left + 1)];            
}int find( int p)
{if( seg[p].w1 == seg[p].w2 ){return seg[p].right - seg[p].left + 1;  }else if( seg[p].left != seg[p].right ){int ret = find( p << 1);if( ret == seg[p<<1].right - seg[p<<1].left + 1 ){ret +=  find( (p << 1) + 1);    }return ret;  }elsereturn 0;
}int sum( int p, int x)
{if( seg[p].left == seg[p].right ){if( seg[p].w1 == seg[p].w2 ){return 1;    }   elsereturn 0;   }    else{int mid = (seg[p].left + seg[p].right) / 2, ret;if( x <= mid ){ret = sum( p << 1, x );if( ret == seg[p<<1].right - x + 1 ) //左子樹滿的
         {ret += find((p << 1) + 1);} }    else{ret = sum( (p << 1) + 1, x );    }return ret; }  
}int main( )
{int N,T, a, b, c, abc = 1;scanf("%d",&T);pre( );while( T-- ){scanf("%s%s",str1,str2);scanf("%d",&N);int len1 = strlen(str1);int len2 = strlen(str2);nmax = len1 < len2 ? len1 : len2;build(0,nmax-1,1);printf("Case %d:\n",abc++);for( int i = 1; i <= N; i++){scanf("%d",&a);if( a == 2 ){scanf("%d",&b);if( b >= nmax ){puts("0");continue;    }printf("%d\n",sum(1,b));        }else{scanf("%d%d%s",&b,&c,str);if( c >= nmax ){// puts("0");continue;}Modify(1,c,str[0], b);}}}return 0;
}