0

これは質問リンクです - QSET - Codechef

これはエディトリアル リンクです - QSET - エディトリアル

基本的に、質問は、ある範囲[L, R]内の部分文字列の数を照会します。この問題を解決するために、セグメント ツリーを実装しました。私は社説を注意深くフォローしました。

structセグメント ツリーのノードを表すを作成しました。

このプログラムを高速化する方法を誰かに説明してもらえますか? ここでは、より高速な I/O が鍵になると思います。そうですか？

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#define ll long long
using namespace std;

struct stnode
{
    ll ans; // the answer for this interval
    ll pre[3]; // pre[i] denotes number of prefixes of interval which modulo 3 give i
    ll suf[3]; // suf[i] denotes number of suffixes of interval which modulo 3 give i
    ll total; // sum of interval modulo 3

    void setLeaf(int value)
    {
        if (value % 3 == 0) ans = 1;
        else ans = 0;
        pre[0] = pre[1] = pre[2] = 0;
        suf[0] = suf[1] = suf[2] = 0;
        pre[value % 3] = 1;
        suf[value % 3] = 1;
        total = value % 3;
    }

    void merge(stnode leftChild, stnode rightChild)
    {
        ans = leftChild.ans + rightChild.ans;
        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 3; j++)
                if ((i + j) % 3 == 0) ans += leftChild.suf[i] * rightChild.pre[j];

        pre[0] = pre[1] = pre[2] = 0;
        suf[0] = suf[1] = suf[2] = 0;
        for (int i = 0; i < 3; i++)
        {
            pre[i] += leftChild.pre[i] + rightChild.pre[(3 - leftChild.total + i) % 3];
            suf[i] += rightChild.suf[i] + leftChild.suf[(3 - rightChild.total + i) % 3];
        }

        total = (leftChild.total + rightChild.total) % 3;
    }
} segtree[400005];

void buildST(string digits, int si, int ss, int se)
{
    if (ss == se)
    {
        segtree[si].setLeaf(digits[ss] - '0');
        return;
    }
    long left = 2 * si + 1, right = 2 * si + 2, mid = (ss + se) / 2;
    buildST(digits, left, ss, mid);
    buildST(digits, right, mid + 1, se);
    segtree[si].merge(segtree[left], segtree[right]);
}

stnode getValue(int qs, int qe, int si, int ss, int se)
{
    if (qs == ss && se == qe)
        return segtree[si];

    stnode temp;
    int mid = (ss + se) / 2;
    if (qs > mid)
        temp = getValue(qs, qe, 2 * si + 2, mid + 1, se);
    else if (qe <= mid)
        temp = getValue(qs, qe, 2 * si + 1, ss, mid);
    else
    {
        stnode temp1, temp2;
        temp1 = getValue(qs, mid, 2 * si + 1, ss, mid);
        temp2 = getValue(mid + 1, qe, 2 * si + 2, mid + 1, se);
        temp.merge(temp1, temp2);
    }
    return temp;
}

void updateTree(int si, int ss, int se, int index, int new_value)
{
    if (ss == se)
    {
        segtree[si].setLeaf(new_value);
        return;
    }

    int mid = (ss + se) / 2;
    if (index <= mid)
        updateTree(2 * si + 1, ss, mid, index, new_value);
    else
        updateTree(2 * si + 2, mid + 1, se, index, new_value);

    segtree[si].merge(segtree[2 * si + 1], segtree[2 * si + 2]);
}

int main()
{
    ios_base::sync_with_stdio(false);
    int n, m; cin >> n >> m;
    string digits; cin >> digits;
    buildST(digits, 0, 0, n - 1);
    while (m--)
    {
        int q; cin >> q;
        if (q == 1)
        {
            int x; int y; cin >> x >> y;
            updateTree(0, 0, n - 1, x - 1, y);
        }
        else
        {
            int c, d; cin >> c >> d;
            cout << getValue(c-1, d-1, 0, 0, n - 1).ans << '\n';
        }
    }
}

大規模なテスト ケース、つまりサブタスク 3 と 4 で TLE を取得しています (問題のページを確認してください)。サブタスク 1 と 2 については、受け入れられます。

[www.codechef.com/viewsolution/5909107] は承認されたソリューションです。scanfの代わりに が使用されることを除いて、コード構造はほとんど同じですcin。でも、私は をオフにしたsync_with_stdioので、それは差別化要因にはなりませんよね?

4

1 に答える 1

0

このプログラムを遅くしている原因がわかりました。buildST関数では、string digits. この関数は再帰的であり、入力がかなり大きいため、文字列のコピーが多数作成され、digits大きなオーバーヘッドが発生します。

char digits[]プログラムの開始時にa を宣言し、メソッドbuildSTを次のように変更しました (基本的には同じですがstring digits、パラメーターとしてはありません。

void buildST(int si, int ss, int se)
{
    if (ss == se)
    {
        segtree[si].setLeaf(digits[ss] - '0');
        return;
    }
    long left = 2 * si + 1, right = 2 * si + 2, mid = (ss + se) / 2;
    buildST(left, ss, mid);
    buildST(right, mid + 1, se);
    segtree[si].merge(segtree[left], segtree[right]);
}

この解決策は受け入れられました。

于 2015-01-18T04:46:20.857 に答える