Мой код получает TLE (превышено ограничение по времени) на онлайн-судье, даже если я закодировал в соответствии с редакцией

Это ссылка на вопрос — QSET — Codechef

Это редакционная ссылка — QSET — редакция

В основном вопрос запрашивает количество подстрок в некотором диапазоне [L, R]. Я реализовал дерево сегментов, чтобы решить этот вопрос. Я внимательно следил за редакцией.

Я создал struct представлять узел дерева сегментов.

Может кто-нибудь объяснить мне, как сделать эту программу быстрее? Я предполагаю, что более быстрый ввод-вывод — вот ключ. Это так?

#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';
}
}
}

Я получаю TLE для более крупных тестовых случаев, то есть подзадач 3 и 4 (проверьте страницу проблемы). Для подзадач 1 и 2 это принимается.

[www.codechef.com/viewsolution/5909107] является приемлемым решением. Он имеет почти такую ​​же структуру кода, за исключением того, что scanf используется вместо cin, Но я выключил sync_with_stdio так что это не должно быть дифференциатором, верно?

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]);
}