V8ITs1 - Online C++0x Compiler & Debugging Tool

#include <bits/stdc++.h>

#define ll long long
#define el cout << '\n'
#define ii pair<int, int>
#define fi first
#define se second

using namespace std;

struct HASH
{
    int n, BASE, MOD;
    string s;
    vector<ll> h, p;

    HASH(int n = 0, int BASE = 0, int MOD = 0, string s = "") :
        n(n), BASE(BASE), MOD(MOD), s(s)
        {
            h.assign(n + 5, 0);
            p.assign(n + 5, 0);
            p[0] = 1;
            for (int i = 1; i <= n; i++)
            {
                h[i] = (h[i - 1] * BASE + s[i]) % MOD;
                p[i] = BASE * p[i - 1] % MOD;
            }
        }
    ll get_hash(int l, int r)
    {
        ll a = h[r] - h[l - 1] * p[r - l + 1] % MOD;
        a %= MOD;
        a += MOD;
        return a % MOD;
    }
};
struct Fenwick_Tree
{
    int maxn;
    vector<ii> bit;

    Fenwick_Tree(int n = 0) : maxn(n)
    {
        bit.assign(n + 5, {0, 0});
    }
    void update(int x, ii v)
    {
        for (;x <= maxn; x += x &- x)
            bit[x] = {bit[x].fi + v.fi, bit[x].se + v.se};
    }
    ii get(int x)
    {
        ii ans = {0, 0};
        for (; x; x &= x - 1)
            ans = {ans.fi + bit[x].fi, ans.se + bit[x].se};
        return ans;
    }
};

const int maxn = 2e5;
const int MOD = 998244353;
const int BASE = 256;

int n, m;
ll ans = 0, sum_y = 0;
string s_1, s_2, fin;
HASH h_1, h_2, h_t;
vector<ii> a, b;
vector<ll> v;
Fenwick_Tree tree;

int bs_prefix(int l, int r)
{
    int pivot = l;
    int ans = 0;
    while (l <= r)
    {
        int m = l + r >> 1;
        ll x = h_1.get_hash(pivot, m);
        ll y = h_t.get_hash(1, m - pivot + 1);
//        cout << pivot << ' ' << m << ' ' << m - pivot + 1 << ' ' << x << ' ' << y, el;
        if (x == y)
        {
            ans = m;
            l = m + 1;
        }
        else
            r = m - 1;
    }
    return ans;
}
int bs_suffix(int l, int r)
{
    int pivot = r;
    int ans = 0;
    while (l <= r)
    {
        int mid = l + r >> 1;
        ll x = h_2.get_hash(mid, pivot);
        ll y = h_t.get_hash(m - (pivot - mid + 1) + 1, m);
//        cout << mid << ' ' << pivot << ' ' << m - (pivot - mid + 1) + 1 << ' ' << m << ' ' << x << ' ' << y, el;
        if (x == y)
        {
            ans = mid ;
            r = mid - 1;
        }
        else
            l = mid + 1;
    }
    return ans;
}
bool cmp(ii a, ii b)
{
    return a.se - a.fi < b.se - b.fi;
}
bool cmp_2(ii a, ii b)
{
    return a.se < b.se || (a.se == b.se && a.fi < b.fi);
}
int get_id(ll x)
{
    return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen("OBSTACLE.INP", "r"))
    {
        freopen("OBSTACLE.INP", "r", stdin);
        freopen("OBSTACLE.OUT", "w", stdout);
    }

    cin >> n >> m;
    cin >> s_1;
    cin >> s_2;
    cin >> fin;

    h_1 = HASH(n, BASE, MOD, " " + s_1);
    h_2 = HASH(n, BASE, MOD, " " + s_2);
    h_t = HASH(m, BASE, MOD, " " + fin);

    for (int i = 1; i <= n; i++)
    {
        int x = bs_prefix(i, min(n, i + m - 1));
        int y = bs_suffix(max(1, i - m + 1), i);
        if (x)
            a.push_back({i, x});
        if (y)
            b.push_back({y, i});
    }
    sort(a.begin(), a.end(), cmp);
    sort(b.begin(), b.end(), cmp);
    for (int i = 0, j = 0; i < a.size(); i++)
    {
        while (j < b.size() && a[i].se - a[i].fi - m >= b[j].fi - b[j].se - 2)
        {
            sum_y += min(0, b[j].se - b[j].fi + 2 - m);
            j++;
        }
        ans += (a[i].se - a[i].fi + 1) * j + sum_y;
    }
    sort(a.begin(), a.end());
    sort(b.begin(), b.end(), cmp_2);
    for (ii pr : a)
        v.push_back(pr.se - pr.fi - m);
    for (ii pr : b)
        v.push_back(pr.fi - pr.se - 2);
    sort(v.begin(), v.end());
//    for (ii pr : a)
//        cout << pr.fi << ' ' << pr.se, el;
//    for (ii pr : b)
//        cout << pr.fi << ' ' << pr.se, el;
    tree = Fenwick_Tree(v.size() + 5);
    for (int i = a.size() - 1, j = b.size() - 1; i >= 0; i--)
    {
        while (j >= 0 && a[i].fi < b[j].se + 2 - m)
        {
            tree.update(get_id(b[j].fi - b[j].se - 2), {1, min(0, b[j].se - b[j].fi + 2 - m)});
            j--;
        }
        ii x = tree.get(get_id(a[i].se - a[i].fi - m));
        ans -= (a[i].se - a[i].fi + 1) * x.fi + x.se;
    }
    tree = Fenwick_Tree(v.size() + 5);
    for (int i = 0, j = 0; i < a.size(); i++)
    {
        while (j < b.size() && b[j].se < a[i].fi)
        {
            tree.update(get_id(b[j].fi - b[j].se - 2), {1, min(0, b[j].se - b[j].fi + 2 - m)});
            j++;
        }
        ii x = tree.get(get_id(a[i].se - a[i].fi - m));
        ans -= (a[i].se - a[i].fi + 1) * x.fi + x.se;
    }
//    for (ii prx : a)
//        for (ii pry : b)
//            if (prx.fi < pry.se + 2 - m)
//                cout << prx.fi << ' ' << prx.se << ' ' << pry.fi << ' ' << pry.se, el;
    cout << ans;
}