P6327 区间加区间 sin 和 题解

· · 题解

维护一个点的 \sin v 和 \cos v

往点里面加入一个值 x 就是

\sin(v + x) = \sin v \cdot \cos x + \cos x \cdot \sin v \cos(v + x) = \cos v \cdot \cos x - \sin x \cdot \sin v

分析代码是否需要维护区间个数：

假设 n 为当前区间的个数，\sin(x_{now}) 为当前的区间 \sin 和 ，\cos(x_{now}) 为当前的区间 \cos 和

首先有

\sum_{i = 1}^{n}\sin (x_i) = \sin(x_{now}) \sum_{i = 1}^{n}\cos (x_i) = \cos(x_{now})

那么区间加入v

\sum_{i = 1}^{n}\sin (x_i + v) &= \sum_{i = 1}^{n}\left[ \sin(x_i)\cos(v) + \cos(x_i)\sin(v) \right] \\\\& =\cos(v)\sum_{i = 1}^{n} \sin(x_i) + \sin(v)\sum_{i=1}^{n}\cos(x_i)\\\\& =\cos(v)\sin(x_{now}) + \sin(v)\cos(x_{now})\\\\& =\sin(x_{now} + v) \end{aligned}

所以只需要往节点里面加 v 即可，不需要维护区间个数

配合模板，主要代码为

using Info = std::array<double, 2>;
/* sin cos */
using Function = i64;
auto mapping = [&](Function f, Info x) -> Info {
    return Info{x[0] * std::cos(f) + x[1] * std::sin(f), x[1] * std::cos(f) - x[0] * std::sin(f)};
};
auto composition = [&](Function f, Function g) -> Function {
    return f + g;
};
auto op = [&](Info lhs, Info rhs) -> Info {
    return Info{lhs[0] + rhs[0], lhs[1] + rhs[1]};
};
auto e = [&]() -> Info {
    return Info{0, 0};
};
auto id = [&]() -> Function {
    return Function{0};
};
unsigned n;
std::cin >> n;
SegmentTree::LazySegTree<Info, Function, mapping, composition, op, e, id> seg(n, [&](auto ...) {
    Info x;
    int a;
    std::cin >> a;
    x[0] = std::sin(a);
    x[1] = std::cos(a);
    return x;
});