E. Hash Swapping | soundhound2018-summer-final-open

方針 O(Qsqrt(N))で間に合いそうなので平方分割を試す

クエリは[l, r)で0-indexedとする。

f(x, i) = 10⁶ⁱ ord(S[x][i])(0<=i<N) とおくと Σ_{l<=i<r}f(x, i) / (10^6l) が解。

平方分割の工夫 g(x, k) = Σ_{kR<=i<=(k+1)R}f(x, i) とおく。 とりあえず[l, r)に含まれるすべての[kR, (k+1)R)について swap(g(x, k), g(y, k)) はわかる。 このとき、f(x, i)、f(y, i)の更新をどうしたらよいか。 愚直にf(x, i)とf(y, i)を交換すると1クエリにO(N)かかってしまう。 そこでR = ceil(sqrt(N))として f'(x, floor(i/R), i mod R) = f(x, i) とする。 ここで vector F[x][R];として F[x][floor(i/R)][i mod R] = f'(x, floow(i/R), i mod R) のようにgを表せば swap(F[x][k], F[y][k])をO(sqrt(N))回繰り返せば済む。

次に[kR, (k+1)R)に収まらないインデックスiについて考える。 この添字の個数はO(sqrt(N))個。 その一通りについて f(x, i)とf(y, i)の値を交換する。(実際には多次元配列Gを使う) その分g(x, floor(i/R))とg(x, floor(i/R))へ足したり引いたりする。O(1)

よって全体でO(Qsqrt(N))

const int MA = 200005, R = 450;
int N, M, ord[20][MA], Q;

mint smo[20][R];
vector<mint> va[20][R];
mint& f(int x, int i) {
    RT va[x][i / R][i%R];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);

    cin >> N >> M;
    rep(i, M) {
        rep(j, R) {
            va[i][j].reserve(R);
            va[i][j].resize(R);
        }

        string s; cin >> s;
        mint pw = 1;
        rep(j, N) {
            ord[i][j] = s[j] - 'a' + 1;
            f(i, j) = pw * ord[i][j];
            smo[i][j / R] += f(i, j);
            pw *= 1000000;
        }
    }

    cin >> Q;
    FOR(t, 1, Q + 1) {
        int typ, x, y, l, r;
        cin >> typ >> x >> y >> l >> r;
        --x; --y; --l;
        if (typ==1) {
            while (l%R && l<r) {
                smo[x][l / R] += f(y, l) - f(x, l);
                smo[y][l / R] += f(x, l) - f(y, l);
                swap(f(x, l), f(y, l));
                l++;
            }
            while (r%R && l < r) {
                r--;
                smo[x][r / R] += f(y, r) - f(x, r);
                smo[y][r / R] += f(x, r) - f(y, r);
                swap(f(x, r), f(y, r));
            }

            for (int i = l; i < r; i += R) {
                int j = i / R;
                swap(smo[x][j], smo[y][j]);
                swap(va[x][j], va[y][j]);
            }
        } else {

            mint re = 0;
            mint pw = mint(1000000).pow(l);

            while (l%R && l<r) {
                re += f(x, l++);
            }
            while (r % R && l < r) {
                re += f(x, --r);
            }
            for (int i = l; i < r; i += R) {
                int j = i / R;
                re += smo[x][j];
            }
            re /= pw;
            cout << re << endl;

        }
    }
}