SoundHound Programming Contest 2018 Masters Tournament 本戦: E - Hash Swapping

https://beta.atcoder.jp/contests/soundhound2018-summer-final-open/tasks/soundhound2018_summer_final_e

問題概要

長さNの文字列がM個与えられる。それらに対するQ個のクエリを順次処理せよ。

  • swapクエリ: x番目の文字列とy番目の文字列の、l番目からr番目の文字を入れ替える
  • hashクエリ: x番目の文字列のハッシュ値(問題文参照)を求めて出力する

N, Q <= 2*105

M <= 20

解法

TL長めなので平方分割でできる。平方分割に関しては前も同じことを書いたが↓の記事を見るのが一番わかりやすいと思う。

なお上の記事だと値をまとめる用のbucketSumと1個1個の値を持っておく用のdataをそれぞれ1個の配列で持っているが、この問題だとswap操作が若干めんどくさいので、bucketSumとdataをそれぞれ区間ごとに細切れにして持っておくみたいなことをしたら実装がある程度簡単になった。

感想

本番平方分割したらいいんじゃねまでは行ったけど全然時間足りず。落ち着いて書き直したら自分の中で平方分割の実装がなんとなく整理ついてきたので次回以降は何卒

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, std.bitmanip;

immutable long MOD = 10^^9 + 7;
immutable long BASE = 10^^6;
immutable int SIZE = 450;
long BUCKET_BASE;

class Node {
    long big;
    long[] small;

    this(string s) {
        small = new long[](SIZE);
        foreach (i; 0..s.length) {
            small[i] = s[i] - 'a' + 1;
        }
        hash;
    }

    void hash() {
        big = 0;
        foreach_reverse (i; 0..SIZE) {
            big = big * BASE % MOD;
            big = (big + small[i]) % MOD;
        }
    }
}


long calc(const Node[] str, int l, int r) {
    long ret = 0;
    foreach_reverse (i; l/SIZE..(r-1)/SIZE+1) {
        int bl = i * SIZE;
        int br = i * SIZE + SIZE;
        if (l > bl || r < br) {
            foreach_reverse (j; max(l, bl)..min(r, br)) {
                ret = ret * BASE % MOD;
                ret = (ret + str[i].small[j%SIZE]) % MOD;
            }
        } else {
            ret = ret * BUCKET_BASE % MOD;
            ret = (ret + str[i].big) % MOD;
        }
    }
    return ret;
}

void nswap(Node[] x, Node[] y, int l, int r) {
    foreach (i; l/SIZE..(r-1)/SIZE+1) {
        int bl = i * SIZE;
        int br = i * SIZE + SIZE;
        if (l > bl || r < br) {
            foreach (j; max(l, bl)..min(r, br)) {
                swap(x[i].small[j%SIZE], y[i].small[j%SIZE]);
            }
            x[i].hash;
            y[i].hash;
        } else {
            swap(x[i].big, y[i].big);
            swap(x[i].small, y[i].small);
        }
    }
}

long powmod(long a, long x, long m) {
    long ret = 1;
    while (x) {
        if (x % 2) ret = ret * a % m;
        a = a * a % m;
        x /= 2;
    }
    return ret;
}

void main() {
    BUCKET_BASE = powmod(BASE, SIZE, MOD);
    auto s = readln.split.map!(to!int);
    auto N = s[0];
    auto M = s[1];
    auto S = M.iota.map!(_ => readln.chomp).array;
    
    auto strs = new Node[][](M, SIZE);
    foreach (i; 0..M) 
        foreach (j; 0..SIZE) 
            if (j*SIZE < N) 
                strs[i][j] = new Node(S[i][j*SIZE..min(N, j*SIZE+SIZE)]);
    
    auto Q = readln.chomp.to!int;
    
    while (Q--) {
        auto q = readln.split.map!(to!int);
        int type = q[0];
        int x = q[1] - 1;
        int y = q[2] - 1;
        int l = q[3] - 1;
        int r = q[4];
        
        if (type == 1) {
            nswap(strs[x], strs[y], l, r);
        } else {
            calc(strs[x], l, r).writeln;
        }
    }
}