HDU - 4339： Query（bitset暴力找下一个为1的）

题意：给定A，B长度相同的字符串，Q次操作，修改操作位单个字符修改，查询操作为询问从某点开始有多少连续相同的字符。

思路：我们把不相同的设为1，相同的设为0，那么询问就是找下一个为1的为位置，可以用线段树解决，可以用set的lower_bound解决，这里用bitset的Find_next函数，效率还可以。 关键是代码短，好写。

复杂度：相当于分块，块的大小为32，所以复杂度为O(L/32)，L取决于下一个1的位置； 可以看讨论：http://codeforces.com/blog/entry/43718

#include<bits/stdc++.h>

using namespace std;

const int maxn=;

bitset<maxn>s;

char a[maxn],b[maxn];

int main()

{

    int T,N,Q,C=,opt;

    scanf("%d",&T);

    while(T--){

        scanf("%s%s",a+,b+); N=strlen(a+);

         s.reset();

         for(int i=;i<=N;i++) if(a[i]!=b[i]) s[i]=; s[N+]=;

         scanf("%d",&Q);

         printf("Case %d:\n",++C);

        while(Q--){

            scanf("%d",&opt);

            if(opt==){

                int w,pos; char c[];

                scanf("%d%d%s",&w,&pos,c);

                if(w==) a[pos+]=c[];

                else b[pos+]=c[];

                if(a[pos+]!=b[pos+]) s[pos+]=;

                else s[pos+]=;

            }

            else {

                int pos; scanf("%d",&pos);

                int first=s._Find_next(pos);

                printf("%d\n",first-pos-);

            }

        }

    }

    return ;

}