2017 ACM-ICPCアジア地区(ウルムチ地区)ネット試合G題Query on a string

3619 ワード

タイトル:
文字列Sと文字列Tを与える
そしてq回クエリー
クエリは2つに分けられます.
1:クエリ文字列区間[x,y]内のTは何回マッチングできるか
2.文字列S[x]をcに変更
問題:
木の配列+でたらめ
木の配列で前のk個の位置を保存して何回Tに一致することができます
i番目の位置が一致するのはS[i~i+len-1]=T[1~len]lenが文字列Tの長さであることを意味する
まずツリー配列を前処理し,クエリ時に直接答えを出し,修正時に文字列を修正してからツリー配列を修正する.Tの長さは最大10であるため直接暴力的に処理できる
code:

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000")
#define inf 0x3f3f3f3f
#define ll long long
#define ull unsigned long long
ll mod = 1e9+7;
const ll INF = 1e18;
typedef pairP;
const double eps = 1e-6;
const int maxn = 1e5+5;
template 
inline bool scan_d(T &ret)
{
    char c;
    int sgn;
    if(c=getchar(),c==EOF) return 0; //EOF
    while(c!='-'&&(c'9')) c=getchar();
    sgn=(c=='-')?-1:1;
    ret=(c=='-')?0:(c-'0');
    while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
    ret*=sgn;
    return 1;
}
inline void out(ll x)
{
    if(x>9) out(x/10);
    putchar(x%10+'0');
}

int lowbit(int p)
{
    return (p&(-p));
}
int n;
int c[maxn];
void add(int p,int num)
{
    while (p<=n)
    {
        c[p]+=num;
        p+=lowbit(p);//    
    }
    return;
}
int query(int p)
{
    int tmp=0;
    while (p)
    {
        tmp+=c[p];
        p-=lowbit(p);//    
    }
    return tmp;
}
char s[maxn];
char t[15];
bool vis[maxn];
int main()
{
    int T;
    cin >> T;
    while(T--) {
        int q;
        scanf("%d", &q);
        scanf("%s", s+1);
        scanf("%s", t+1);
        int lens = strlen(s+1);
        int lent = strlen(t+1);
        n = lens;
        memset(vis, false, sizeof(vis));
        memset(c, 0, sizeof(c));
        for(int i=1; i+lent-1<=lens; i++) {
            bool f = true;
            for(int j=1; j<=lent; j++) {
                if(s[i+j-1]!=t[j]) {
                    f = false;
                    break;
                }
            }
            if(f) {
                add(i, 1);
                vis[i] = true;
            }
        }
        while(q--) {
            char c;
            scanf("
%c", &c);
            if(c=='Q') {
                int x, y;
                scanf("%d%d", &x, &y);
                y -= lent;
                y++;
                if(x <= y)
                    printf("%d
", query(y)-query(x-1));
                else
                    puts("0");
            }
            else {
                int x;
                char y;
                scanf("%d %c", &x, &y);
                s[x] = y;
                for(int i=max(1, x-lent+1); i<=min(lens-lent+1, x); i++) {
                    int f = 1;
                    for(int j=1; j<=lent; j++) {
                        if(s[i+j-1]!=t[j]) {
                            f = 0;
                            break;
                        }
                    }
                    if(f != vis[i]) {
                        if(vis[i])
                            add(i, -1);
                        else
                            add(i, 1);
                        vis[i] = !vis[i];
                    }
                }
            }
        }
        puts("");
    }
}

[PHPStan] Consider adding something like array<Foo> to the PHPDoc. が Level=max で発生する場合の対処法

一元疎多項式計算機