Как корректно комбинировать две ленивые операции (умножить и прибавить на отрезке)?
Задача: на отрезке нужно уметь a[i] = a[i]*b и a[i] = a[i]+c, плюс запрос суммы по модулю. Две разные ленивые операции висят одновременно. Как их хранить и проталкивать, чтобы порядок не сломался?
2 ответа
Представьте композицию аффинным преобразованием x -> mul*x + add (всё по модулю). Любая последовательность умножений и прибавлений сворачивается в одну такую пару (mul, add). Нейтраль — (1, 0).
Ключ — закон композиции. Если сначала применили (m1, a1), потом (m2, a2), итог:
x -> m2*(m1*x + a1) + a2 = (m2*m1) * x + (m2*a1 + a2)
Значит новая пометка (m2*m1 mod p, (m2*a1 + a2) mod p).
const long long MOD = 1e9+7;
long long t[4*N], mul[4*N], add[4*N];
void applyOp(int v, int tl, int tr, long long m, long long c) {
long long len = tr - tl + 1;
t[v] = (m * t[v] + c % MOD * len) % MOD;
mul[v] = (mul[v] * m) % MOD;
add[v] = (add[v] * m + c) % MOD;
}
void push(int v, int tl, int tr) {
int tm = (tl + tr) / 2;
applyOp(2*v, tl, tm, mul[v], add[v]);
applyOp(2*v+1, tm+1, tr, mul[v], add[v]);
mul[v] = 1; add[v] = 0;
}
Инициализируйте mul[v]=1, add[v]=0 для всех узлов. Сложность O(log n) на операцию. Это общий рецепт: ленивые операции должны образовывать моноид (есть нейтраль и ассоциативная композиция) — тогда их можно складывать в одну пометку.
Тонкость с порядком: в applyOp я обновляю t[v] до изменения mul[v]/add[v], и формула add[v] = add[v]*m + c ставит новую операцию после уже накопленной. Это соответствует тому, что новая операция применяется к данным позже. Если перепутать (add[v] = add[v] + c*mul[v] или поменять местами) — получите WA на тестах, где умножение и сложение чередуются.
Проверяйте композицию на крошечном примере вручную: возьмите x=2, примените +3 затем ×4 → 20, и убедитесь, что свёрнутая пара (4, 12) даёт 4*2+12 = 20. Такая ручная сверка экономит часы отладки.