题目链接:Click here~~
题意:
有s1、s2两个串,有两种操作:1、查询从i位置开始,两串中最多有多少个字符相等。2、将某串的i位置的字符变为其他字符。
解题思路:
用一棵树状数组记录两串中前 i 个位置共有多少个字符对应相等。
若某段区间[i,j]中,字符全部对应相等,则必有sum(j)-sum(i-1) = j-i+1 。
设字符串长度为n,则操作1中我们要找的是k = max{ j } (j∈[i,n] && sum(j)-sum(i-1) = j-i+1)
则我们可以通过这个条件二分得到k的值。
首先,先假设k是n。此时我们需要考虑的区间是[i,n]。
先取中间值mid=(i+n)/2,将区间分成两部分。
判断左区间是否满足条件,如果满足,只需要考虑右区间,则让区间的左端点等于mid+1。
如果不满足,则右区间一定不满足,即只需要考虑左区间,让区间的右端点等于mid-1。
当区间变为一个点时,我们就找到了k。
#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; #define FileIn freopen("in.ads","r",stdin) #define FileOut freopen("out.ads","w",stdout) #define N 1000005 int n,c[N]; char s[2][N],ch; int lowbit(int x) { return x & -x; } void add(int loc,int x) { while(loc <= n) { c[loc] += x; loc += lowbit(loc); } } int sum(int loc) { int ans = 0; while(loc > 0) { ans += c[loc]; loc -= lowbit(loc); } return ans; } int Binary(int l,int r) { while(l < r) { int mid = (l+r)/2; if(sum(mid)-sum(l-1) == mid-l+1) l = mid+1; else r = mid; } return r-1; } int main() { int z,Q,cmd,loc,num,ncase = 0; scanf("%d",&z); while(z--) { printf("Case %d:\n",++ncase); memset(c,0,sizeof(c)); scanf("%s%s",s[0]+1,s[1]+1); n = min(strlen(s[0]+1),strlen(s[1]+1)); for(int i=1;i<=n;i++) if(s[0][i] == s[1][i]) add(i,1); scanf("%d",&Q); while(Q--) { scanf("%d",&cmd); if(cmd == 2) { scanf("%d",&loc); printf("%d\n",Binary(loc+1,n+1)-loc); } else { scanf("%d%d %c",&num,&loc,&ch); if(loc+1 > n || s[num-1][loc+1] == ch) continue; if(s[num-1][loc+1] == s[(num-1)^1][loc+1]) add(loc+1,-1); else if(ch == s[(num-1)^1][loc+1]) add(loc+1,1); s[num-1][loc+1] = ch; } } } return 0; }