懒更新|单点查询

lc1636带懒标记的区间加法、乘法、单点查询的实现全局 add、mul 懒标记代替逐个修改元素append 时用费马小定理求逆元还原原值查询时 O(1) 计算真实值时间复杂度全操作 O(logMOD)class Fancy {static constexpr int MOD 1000000007;vectorint vals;long long add 0;long long mul 1;long long pow(long long x, int n) {long long res 1;for (; n; n / 2) {if (n % 2) {res res * x % MOD;}x x * x % MOD;}return res;}public:void append(int val) {// 注意这里有减法计算结果可能是负数MOD 可以保证计算结果非负vals.push_back((val - add MOD) * pow(mul, MOD - 2) % MOD);}void addAll(int inc) {add (add inc) % MOD;}void multAll(int m) {mul mul * m % MOD;add add * m % MOD;}int getIndex(int idx) {if (idx vals.size()) {return -1;}return (vals[idx] * mul add) % MOD;}};