A 隔离
二分答案，简单\(check\)一下即可
code
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<iostream>
#include<random>using namespace std;typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;const int maxn = 100005;
inline ll read(){ll x = 0; char c = getchar();while(c < '0' || c > '9')c = getchar();do{x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}while(c <= '9' && c >= '0');return x;
}
int n, m;
struct node{ll l, r;}d[maxn];
bool cmp(node x, node y){return x.l < y.l;}
bool check(ll mid){ll las = -1e18;int p = 1;for(int i = 1; i <= n; ++i){while(p <= m && d[p].r < las + mid)++p;if(p > m)return false;las = max(las + mid, d[p].l);}return true;
}
int main(){n = read(), m = read();for(int i = 1; i <= m; ++i)d[i].l = read(), d[i].r = read();sort(d + 1, d + m + 1, cmp);ll l = 0, r = 1e18, ans = 0;while(l <= r){ll mid = (l + r) >> 1;if(check(mid))ans = mid, l = mid + 1;else r = mid - 1;}printf("%lld\n",ans);return 0;
}
B 绽放的花火
首先发现维度是假的，只要知道 \(\sum n_i\) 即可
设 \(f_i\) 表示从 \(i\) 到第 \(i +1\) 号点的期望步数
每次有 \(p\) 的概率到 \(i +1\)， \(1 - p\) 的概率到 \(i - 1\) ， 到 \(i - 1\) 还需要 \(f_{i -1} + f_i\) 才能到 \(i +1\)
那么 $f_i = 1 + (1 - p) (f_i + f_{i - 1}) $
移项即可得到递推公式， 然后到 \(\sum n_i\) 的期望步数就是 \(\sum f_i\)
code
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<iostream>
#include<random>using namespace std;typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;const int maxn = 500005;
const int mod = 1e9 + 7;
inline int read(){int x = 0; char c = getchar();while(c < '0' || c > '9')c = getchar();do{x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}while(c <= '9' && c >= '0');return x;
}
int n, sum, p;
int f[maxn];
ll qpow(int x, int y){ll ans = 1;for(; y; y >>= 1, x = 1ll * x * x % mod)if(y & 1)ans = 1ll * ans * x % mod;return ans;
}
int main(){int t = read();for(int ask = 1; ask <= t; ++ask){n = read(); sum = 0;for(int i = 1; i <= n; ++i)sum += read();sum = sum - n + 1;p = read();int invp = qpow(p, mod - 2);f[1] = 1;for(int i = 2; i < sum; ++i)f[i] = 1ll * invp * ((1ll * (1 - p + mod) * f[i - 1] % mod + 1) % mod) % mod;int ans = 0;for(int i = 1; i < sum; ++i)ans = (ans + f[i]) % mod;for(int i = 1; i < sum; ++i)printf("%d ",f[i]);printf("%d\n",ans);} return 0;
}
C 美化数列
线段树维护等差数列，等比数列，对应加斐波那契数列
等差好处理， 维护首项 \(k\)， 以及公差 \(d\)， 因为是加法， 所以首项和公差都有可加性
等比数列， 发现公比 \(D\) 是固定的，那么首项就可以直接相加，预处理 \(D^n\) 可以快速求首项， 区间和预处理 \(\sum_{i= 1}^n D^i\)即可
对应加斐波那契， 发现对应区间加一段斐波那契，可以转化为对应区间加上 \(f1\) 倍的从 \(fib_1\) 开始的序列， \(f2\) 倍从 \(fib_2\) 开始的序列， 预处理 \(fib\) 每一项是多少 \(fib_1\) 和 \(fib_2\) 构成的即可快速 \(push\_down\)
码量感人
code
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<iostream>
#include<random>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int maxn = 100005;
const int mod = 19260817;
const int inv2 = 9630409;
inline int read(){int x = 0; char c = getchar();while(c < '0' || c > '9')c = getchar();do{x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}while(c <= '9' && c >= '0');return x;
}
int fib[maxn], a[maxn], dpow[maxn], sd[maxn], f1[maxn], f2[maxn], sb[maxn], sf1[maxn], sf2[maxn];
int n, m, D;
struct tree{struct node{int sum, k1, d, k2, f1, f2; }t[maxn << 2 | 1];void push_up(int x){t[x].sum = (t[x << 1].sum + t[x << 1 | 1].sum) % mod;}void push_down(int x, int l, int r){int mid = (l + r) >> 1, ls = x << 1, rs = x << 1 | 1;if(t[x].d || t[x].k1){t[ls].d = (t[ls].d + t[x].d) % mod;t[rs].d = (t[rs].d + t[x].d) % mod;int nk = (t[x].k1 + 1ll * (mid + 1 - l) * t[x].d % mod) % mod;t[ls].k1 = (t[ls].k1 + t[x].k1) % mod;t[rs].k1 = (t[rs].k1 + nk) % mod;t[ls].sum = (t[ls].sum + 1ll * (t[x].k1 + 1ll * (mid - l) * t[x].d % mod + t[x].k1) % mod * (mid - l + 1) % mod * inv2 % mod) % mod;t[rs].sum = (t[rs].sum + 1ll * (nk + 1ll * (r - mid - 1) * t[x].d % mod + nk) % mod * (r - mid) % mod * inv2 % mod) % mod;t[x].k1 = t[x].d = 0;}if(t[x].k2){t[ls].k2 = (t[x].k2 + t[ls].k2) % mod;int nk = 1ll * t[x].k2 * dpow[mid + 1 - l] % mod;t[rs].k2 = (nk + t[rs].k2) % mod;t[ls].sum = (t[ls].sum + 1ll * t[x].k2 * sd[mid - l] % mod) % mod;t[rs].sum = (t[rs].sum + 1ll * nk * sd[r - mid - 1] % mod) % mod;t[x].k2 = 0;}if(t[x].f1 || t[x].f2){t[ls].f1 = (t[ls].f1 + t[x].f1) % mod;t[ls].f2 = (t[ls].f2 + t[x].f2) % mod;int len = mid - l + 1 ;t[ls].sum = (t[ls].sum + 1ll * t[x].f1 * sb[len] % mod + 1ll * t[x].f2 * (sb[len + 1] - 1) % mod) % mod;int nf1 = 1ll * t[x].f1 * f1[len + 1] % mod + 1ll * t[x].f2 * f1[len + 2] % mod;int nf2 = 1ll * t[x].f1 * f2[len + 1] % mod + 1ll * t[x].f2 * f2[len + 2] % mod;t[rs].f1 = (t[rs].f1 + nf1) % mod;t[rs].f2 = (t[rs].f2 + nf2) % mod;t[rs].sum = (t[rs].sum + 1ll * nf1 * sb[r - mid] % mod + 1ll * nf2 * (sb[r - mid + 1] - 1) % mod) % mod;t[x].f1 = t[x].f2 = 0; }}void built(int x, int l, int r){if(l == r){t[x].sum = a[l];return;}int mid = (l + r) >> 1;built(x << 1, l, mid);built(x << 1 | 1, mid + 1, r);push_up(x);}void modify_dc(int x, int l, int r, int L, int R, int k, int d){if(L <= l && r <= R){t[x].k1 = (t[x].k1 + k) % mod;t[x].d = (t[x].d + d) % mod;t[x].sum = (t[x].sum + 1ll * (k + 1ll * (r - l) * d % mod + k) % mod * (r - l + 1) % mod * inv2 % mod) % mod;return;}push_down(x, l, r);int mid = (l + r) >> 1;if(L <= mid) {modify_dc(x << 1, l, mid, L, R, k, d);k = (k + 1ll * (mid - max(L, l) + 1) * d % mod) % mod;}if(R > mid) modify_dc(x << 1 | 1, mid + 1, r, L, R, k, d);push_up(x);}void modify_db(int x, int l, int r, int L, int R, int k){if(L <= l && r <= R){t[x].k2 = (t[x].k2 + k) % mod;t[x].sum = (t[x].sum + 1ll * sd[r - l] * k) % mod;return;}push_down(x, l, r);int mid = (l + r) >> 1;if(L <= mid){modify_db(x << 1, l, mid, L, R, k);k = 1ll * k * dpow[mid - max(l, L) + 1] % mod;}if(R > mid)modify_db(x << 1 | 1, mid + 1, r, L, R, k);push_up(x);}void modify_fib(int x, int l, int r, int L, int R, int nf1, int nf2){if(L <= l && r <= R){t[x].sum = (0ll + t[x].sum + 1ll * nf1 * sb[r - l + 1] % mod + 1ll * nf2 * (sb[r - l + 2] - 1) % mod) % mod;t[x].f1 = (t[x].f1 + nf1) % mod;t[x].f2 = (t[x].f2 + nf2) % mod;return;}push_down(x, l, r);int mid = (l + r) >> 1;if(L <= mid){modify_fib(x << 1, l, mid, L, R, nf1, nf2);int len = mid + 2 - max(l, L), lf1 = nf1, lf2 = nf2;nf1 = 1ll * lf1 * f1[len] % mod + 1ll * lf2 * f1[len + 1] % mod;nf2 = 1ll * lf1 * f2[len] % mod + 1ll * lf2 * f2[len + 1] % mod;}if(R > mid)modify_fib(x << 1 | 1, mid + 1, r, L, R, nf1, nf2);push_up(x);}int query(int x, int l, int r, int L, int R){if(L <= l && r <= R)return t[x].sum;push_down(x, l, r);int mid = (l + r) >> 1, ans = 0;if(L <= mid)ans += query(x << 1, l, mid, L, R);if(R > mid)ans = (ans + query(x << 1 | 1, mid + 1, r, L, R)) % mod;return ans % mod;}
}t;
int main(){n = read(), m = read(), D = read();for(int i = 1; i <= n; ++i)a[i] = read();t.built(1, 1, n);for(int i = 1; i <= n; ++i)a[i] = 0;dpow[0] = 1; for(int i = 1; i <= n; ++i)dpow[i] = 1ll * dpow[i - 1] * D % mod;sd[0] = 1; for(int i = 1; i <= n; ++i)sd[i] = (sd[i - 1] + dpow[i]) % mod;fib[1] = fib[2] = 1; f1[1] = f2[2] = 1;for(int i = 3; i <= n; ++i)fib[i] = (fib[i - 1] + fib[i - 2]) % mod;for(int i = 3; i <= n; ++i)f1[i] = (f1[i - 1] + f1[i - 2]) % mod;for(int i = 3; i <= n; ++i)f2[i] = (f2[i - 1] + f2[i - 2]) % mod;for(int i = 1; i <= n; ++i)sb[i] = (sb[i - 1] + fib[i]) % mod;for(int i = 1; i <= m; ++i){int o = read(), l = read(), r = read();if(o == 1){int k = read(), d = read();t.modify_dc(1, 1, n, l, r, k, d);}if(o == 2){int k = read();t.modify_db(1, 1, n, l, r, k);}if(o == 3) t.modify_fib(1, 1, n, l, r, 1, 0);if(o == 4) printf("%d\n",t.query(1, 1, n, l, r));} return 0;
}
D ZB的旋转树
弃
