https://yukicoder.me/problems/no/753
dp[level][bit][winner]:level段のトーナメントをbitに属す挑戦者で作る。勝者がwinnerの時の場合の数
として求めます。高速化いろいろしてAC。
https://yukicoder.me/problems/no/749
和と積のクエリが混ざっている時ってこうやれば良いんですね。解説で群論による考え方が記載されていたのであとで読みたいですね。
ai->kは0を掛けてkを足すクエリに言い換えられます。
struct segtree {
int n; vl sum, add, mul, fib;
void init(int mx) {
n = 1;
while(n < mx) n *= 2;
sum = vl(n * 2, 0);
add = vl(n * 2, 0);
mul = vl(n * 2, 1);
fib = vl(n * 2, 0);
}
segtree(int mx = 0) { init(mx); }
inline void lazy_eval(int k, int l, int r) {
int m = (l + r) / 2;
if(add[k] || mul[k] != 1 || fib[k]) {
MUL(sum[k * 2 + 1], mul[k]);
ADD(sum[k * 2 + 1], (vx[m] - vx[l] + mod) * add[k] % mod);
ADD(sum[k * 2 + 1], (F[vx[m]] - F[vx[l]] + mod) * fib[k] % mod);
MUL(mul[k * 2 + 1], mul[k]);
MUL(add[k * 2 + 1], mul[k]);
MUL(fib[k * 2 + 1], mul[k]);
ADD(add[k * 2 + 1], add[k]);
ADD(fib[k * 2 + 1], fib[k]);
MUL(sum[k * 2 + 2], mul[k]);
ADD(sum[k * 2 + 2], (vx[r] - vx[m] + mod) * add[k] % mod);
ADD(sum[k * 2 + 2], (F[vx[r]] - F[vx[m]] + mod) * fib[k] % mod);
MUL(mul[k * 2 + 2], mul[k]);
MUL(add[k * 2 + 2], mul[k]);
MUL(fib[k * 2 + 2], mul[k]);
ADD(add[k * 2 + 2], add[k]);
ADD(fib[k * 2 + 2], fib[k]);
add[k] = 0;
mul[k] = 1;
fib[k] = 0;
}
}
void addapp(int a, int b, ll s, int k, int l, int r) {
if(b <= l || r <= a) return;
if(a <= l && r <= b) {
ADD(sum[k], (vx[r] - vx[l] + mod) * s % mod);
ADD(add[k], s);
}
else {
lazy_eval(k, l, r);
addapp(a, b, s, k * 2 + 1, l, (l + r) / 2);
addapp(a, b, s, k * 2 + 2, (l + r) / 2, r);
sum[k] = (sum[k * 2 + 1] + sum[k * 2 + 2]) % mod;
}
}
void mulapp(int a, int b, ll s, int k, int l, int r) {
if(b <= l || r <= a) return;
if(a <= l && r <= b) {
MUL(sum[k], s);
MUL(add[k], s);
MUL(mul[k], s);
MUL(fib[k], s);
}
else {
lazy_eval(k, l, r);
mulapp(a, b, s, k * 2 + 1, l, (l + r) / 2);
mulapp(a, b, s, k * 2 + 2, (l + r) / 2, r);
sum[k] = (sum[k * 2 + 1] + sum[k * 2 + 2]) % mod;
}
}
void fibapp(int a, int b, ll s, int k, int l, int r) {
if(b <= l || r <= a) return;
if(a <= l && r <= b) {
ADD(sum[k], (F[vx[r]] - F[vx[l]] + mod) * s % mod);
ADD(fib[k], s);
}
else {
lazy_eval(k, l, r);
fibapp(a, b, s, k * 2 + 1, l, (l + r) / 2);
fibapp(a, b, s, k * 2 + 2, (l + r) / 2, r);
sum[k] = (sum[k * 2 + 1] + sum[k * 2 + 2]) % mod;
}
}
ll ga(int a, int b, int k, int l, int r) {
if(b <= l || r <= a) return ll();
if(a <= l && r <= b) return sum[k];
else {
lazy_eval(k, l, r);
ll lv = ga(a, b, k * 2 + 1, l, (l + r) / 2);
ll rv = ga(a, b, k * 2 + 2, (l + r) / 2, r);
return (lv + rv) % mod;
}
}
void show() {
vector<ll> tmp;
rep(i, 0, n) tmp.push_back(get(i, i + 1));
debug(tmp);
}
ll get(int a, int b) { return ga(a, b, 0, 0, n); }
void addupdate(int a, int b, ll s) { addapp(a, b, s, 0, 0, n); }
void mulupdate(int a, int b, ll s) { mulapp(a, b, s, 0, 0, n); }
void fibupdate(int a, int b, ll s) { fibapp(a, b, s, 0, 0, n); }
};
https://yukicoder.me/problems/no/255
前の問題のsegtreeをそのまま使えます。