题解 accoders::NOI 5508【漂亮大厨（cook）】
part 1
区间加 \(x\)，区间询问有多少个数字 \(\leq y\)。\(n,m\leq 10^5,x\leq 200,y\leq 10^7\)。
考虑 P5356 [Ynoi2017] 由乃打扑克 的做法，分块，块内按照值排序。修改就整块打 tag，散块暴力重构（可以归并排序重构）；询问在整块上二分，散块暴力。这样的复杂度是 \(O(n\log n\cdot\sqrt n)\)，瓶颈来自整块上的二分。由于这题不是由乃打扑克，询问可以离线，所以考虑离线所有对整块的询问（散块直接暴力不管；离线询问时先减掉加法标记；重构散块时，新建这个块的副本，以后的询问挂在副本上）。离线完了以后一共有 \(O(\sqrt n+q)\) 个整块挂了总共 \(O(q\sqrt n)\) 个询问，考虑在每个整块上对询问排序后用一个指针扫边所有块，这样就能取得所有询问的答案，做到了 \(O(n\sqrt n)\)。
part 2
\(Q\) 次询问每次给定 \(n, m\) 求 \(\sum_{i\leq m}\binom n i\)。\(Q, n, m\leq 10^5\)。
可以莫队，\(m\) 那一维就直接加或减一个组合数。\(n\) 那一维就是按照 \(\binom n m = \binom{n-1} m + \binom{n-1}{m-1}\) 展开一次，变成两倍的形式再调调系数。
code
// ubsan: undefined
// accoders
#include <tuple>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cassert>
#include <algorithm>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define debug(...) void(0)
#endif
typedef long long LL;
template <unsigned P>
struct modint {
unsigned v;
modint() : v(0) {}
template <class T>
modint(T x) {
x %= (int)P, v = x < 0 ? x + P : x;
}
modint operator+() const { return *this; }
modint operator-() const { return modint(0) - *this; }
modint inv() const { return assert(v), qpow(*this, P - 2); }
friend int raw(const modint &self) { return self.v; }
template <class T>
friend modint qpow(modint a, T b) {
modint r = 1;
for (; b; b >>= 1, a *= a)
if (b & 1)
r *= a;
return r;
}
modint &operator+=(const modint &rhs) {
if (v += rhs.v, v >= P)
v -= P;
return *this;
}
modint &operator-=(const modint &rhs) {
if (v -= rhs.v, v >= P)
v += P;
return *this;
}
modint &operator*=(const modint &rhs) {
v = 1ull * v * rhs.v % P;
return *this;
}
modint &operator/=(const modint &rhs) { return *this *= rhs.inv(); }
friend modint operator+(modint lhs, const modint &rhs) { return lhs += rhs; }
friend modint operator-(modint lhs, const modint &rhs) { return lhs -= rhs; }
friend modint operator*(modint lhs, const modint &rhs) { return lhs *= rhs; }
friend modint operator/(modint lhs, const modint &rhs) { return lhs /= rhs; }
friend bool operator==(const modint &lhs, const modint &rhs) { return lhs.v == rhs.v; }
friend bool operator!=(const modint &lhs, const modint &rhs) { return lhs.v != rhs.v; }
};
typedef modint<998244353> mint;
template <int N>
struct C_prime {
mint fac[N + 10], ifac[N + 10];
C_prime() {
fac[0] = ifac[0] = 1;
for (int i = 1; i <= N; i++) fac[i] = fac[i - 1] * i;
ifac[N] = 1 / fac[N];
for (int i = N; i >= 1; i--) ifac[i - 1] = ifac[i] * i;
}
mint operator()(int n, int m) const { return n >= m ? fac[n] * ifac[m] * ifac[n - m] : 0; }
};
template <int N, int unit>
struct Jason42 {
vector<pair<int, int>> blo[N / unit + 10];
int bel[N + 10], tag[N / unit + 10];
void init(int n, int b[]) {
for (int i = 1; i <= n; i++) bel[i] = (i - 1) / unit + 1;
for (int i = 1; i <= n; i++) {
blo[bel[i]].emplace_back(b[i], i);
}
for (int b = 1; b <= bel[n]; b++) sort(blo[b].begin(), blo[b].end());
}
void modify_bf(int L, int R, int b, int k) {
for (auto &ccf : blo[b]) {
if (L <= ccf.second && ccf.second <= R)
ccf.first += k;
}
sort(blo[b].begin(), blo[b].end());
}
void modify(int L, int R, int k) {
int Lb = bel[L], Rb = bel[R];
for (int i = Lb + 1; i < Rb; i++) tag[i] += k;
if (Lb == Rb)
modify_bf(L, R, Lb, k);
else
modify_bf(L, R, Lb, k), modify_bf(L, R, Rb, k);
}
int count_bf(int L, int R, int b, int lim) {
int ans = 0;
for (auto &ccf : blo[b]) {
if (L <= ccf.second && ccf.second <= R)
ans += ccf.first + tag[b] <= lim;
}
return ans;
}
int count_blo(int b, int lim) {
// int bfr = count_bf(1, N, b, lim);
int orz = upper_bound(blo[b].begin(), blo[b].end(), pair<int, int>{ lim - tag[b], 998244353 }) -
blo[b].begin();
// if (bfr != orz) debug("count: bf = %d, st = %d, assert(0)\n", bfr, orz);
return orz;
}
int count(int L, int R, int lim) {
int Lb = bel[L], Rb = bel[R], ans = 0;
for (int i = Lb + 1; i < Rb; i++) ans += count_blo(i, lim);
if (Lb == Rb)
ans += count_bf(L, R, Lb, lim);
else
ans += count_bf(L, R, Rb, lim) + count_bf(L, R, Lb, lim);
return ans;
}
};
template <int N, int unit>
struct RobinBruteForce {
int a[N + 10];
void init(int n, int b[]) {
for (int i = 1; i <= n; i++) a[i] = b[i];
}
void modify(int L, int R, int k) {
for (int i = L; i <= R; i++) a[i] += k;
}
int count(int L, int R, int lim) {
int ans = 0;
for (int i = L; i <= R; i++) ans += a[i] <= lim;
return ans;
}
};
mint ans[1 << 17];
C_prime<1 << 17> binom;
struct Moqueue {
vector<tuple<int, int, int>> vec;
void add(int n, int m, int id) {
debug("add(%d, %d, %d)\n", n, m, id);
vec.emplace_back(n, min(n, m), id);
}
void answer() {
sort(vec.begin(), vec.end(), [](tuple<int, int, int> a, tuple<int, int, int> b) {
int l1, r1, l2, r2;
tie(l1, r1, ignore) = a, tie(l2, r2, ignore) = b;
return l1 / 356 != l2 / 356 ? l1 < l2 : r1 < r2;
});
int nowl = 0, nowr = 0;
mint now = 1, inv2 = mint(1) / 2;
for (auto &&qry : vec) {
int l, r, id;
tie(l, r, id) = qry;
// l >= r
while (nowl < l) now = now * 2 - binom(nowl++, nowr);
while (nowr > r) now -= binom(nowl, nowr--);
while (nowl > l) now = (now + binom(--nowl, nowr)) * inv2;
while (nowr < r) now += binom(nowl, ++nowr);
ans[id] = now;
}
}
};
int n, Q, Qcnt, ia[1 << 17];
Jason42<100010, 356> Robin;
// RobinBruteForce<100010, 356> Robin;
Moqueue moqueue;
int main() {
freopen("cook.in", "r", stdin);
freopen("cook.out", "w", stdout);
scanf("%d%d", &n, &Q);
for (int i = 1; i <= n; i++) scanf("%d", ia + i);
Robin.init(n, ia);
for (int i = 1, op, l, r, x, y, k; i <= Q; i++) {
scanf("%d%d%d", &op, &l, &r);
if (op == 1)
scanf("%d", &x), Robin.modify(l, r, x);
else
scanf("%d%d", &y, &k), moqueue.add(Robin.count(l, r, y), k, ++Qcnt);
}
moqueue.answer();
for (int i = 1; i <= Qcnt; i++) printf("%d\n", raw(ans[i]));
return 0;
}