【洛谷】P4588 [TJOI2018] 数学计算 的题解 + 线段树板子代码

【洛谷】P4588 [TJOI2018] 数学计算 的题解 + 线段树板子代码

洛谷传送门

题解

论我的快读快写的神奇故事

用快读快写直接整出了这种逆天，不用快读，神奇！！！

划水一个线段树 $+$ 离散化。

一如既往的打了一个暴力，神奇的一分不得。果然线段树的威力在这里qaq

总体思路就是将数据按时间排序，建线段树，维护区间乘。这样的话根节点就是到现在为止的所有数的乘积。

代码

#include <bits/stdc++.h>
#define lowbit(x) x & (-x)
#define endl "\n"
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
namespace fastIO {inline int read() {register int x = 0, f = 1;register char c = getchar();while (c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();return x * f;}inline void write(int x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');return;}
}
using namespace fastIO;
int T, q, op, m;
ll mod, sum[1000005];
void update(int now) {sum[now] = (sum[now << 1] * sum[now << 1|1]) % mod;
}
void build(int now, int l, int r) {if(l == r) {sum[now] = 1;return;}int mid = (l + r) >> 1;build(now << 1, l, mid);build(now << 1|1, mid + 1, r);update(now);
}
void change(int c, int l, int r, int L, int R, int p) {if(l >= L && r <= R) {sum[c] = p;return;}int mid = (l + r) >> 1;if(L <= mid) change(c << 1, l, mid, L, R, p);if(R > mid) change(c << 1 | 1, mid + 1, r, L, R, p);update(c);
}
int main() {//freopen(".in","r",stdin);//freopen(".out","w",stdout);ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin >> T;for(int i = 1; i <= T; i ++) {cin >> q >> mod;build(1, 1, q); for(int i = 1; i <= q; i ++) {cin >> op >> m;if(op == 1) {change(1, 1, q, i, i, m);sum[1] %= mod;}else {change(1, 1, q, m, m, 1);}cout << sum[1] % mod << endl;}}return 0;
}

附加

其实这就是一个有一点点像线段树板子，总体来说没有什么难度，线段树的话，其实只要写熟练了以后，基本就很简单了。

很多大佬在 NOIP 的比赛前都会打一遍线段树，可见这个的重要性了吧。

这里也给出两个线段树的板子题的代码。

【洛谷】P3372 【模板】线段树 1

题目传送门

代码

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
ll n, a[100005], d[270005], b[270005];
void build(ll l, ll r, ll p) {  if (l == r) {d[p] = a[l];  return;}ll m = l + ((r - l) >> 1);build(l, m, p << 1), build(m + 1, r, (p << 1) | 1); d[p] = d[p << 1] + d[(p << 1) | 1];
}
void update(ll l, ll r, ll c, ll s, ll t, ll p) {if (l <= s && t <= r) {d[p] += (t - s + 1) * c, b[p] += c;return;}ll m = s + ((t - s) >> 1);if (b[p])d[p << 1] += b[p] * (m - s + 1), d[(p << 1) | 1] += b[p] * (t - m), b[p << 1] += b[p], b[(p << 1) | 1] += b[p];b[p] = 0;if (l <= m)update(l, r, c, s, m, p << 1);if (r > m) update(l, r, c, m + 1, t, (p << 1) | 1);d[p] = d[p << 1] + d[(p << 1) | 1]; 
}
ll getsum(ll l, ll r, ll s, ll t, ll p) {if (l <= s && t <= r) return d[p];ll m = s + ((t - s) >> 1);if (b[p])d[p << 1] += b[p] * (m - s + 1), d[(p << 1) | 1] += b[p] * (t - m), b[p << 1] += b[p], b[(p << 1) | 1] += b[p];b[p] = 0;ll sum = 0;if (l <= m)sum =getsum(l, r, s, m, p << 1);if (r > m) sum += getsum(l, r, m + 1, t, (p << 1) | 1);return sum;
}
int main() {//freopen(".in","r",stdin);//freopen(".out","w",stdout);ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);ll q, i1, i2, i3, i4;cin >> n >> q;for (ll i = 1; i <= n; i++) cin >> a[i];build(1, n, 1);while (q--) {cin >> i1 >> i2 >> i3;if (i1 == 2)cout << getsum(i2, i3, 1, n, 1) << endl;elsecin >> i4, update(i2, i3, i4, 1, n, 1);}return 0;
}

【洛谷】P3373 【模板】线段树 2

题目传送门

代码

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
inline ll read() {register ll x = 0, f = 1;register char c = getchar();while (c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();return x * f;
}
int n, m;
ll mod;
ll a[100005], sum[400005], mul[400005], laz[400005];
void up(int i) { sum[i] = (sum[(i << 1)] + sum[(i << 1) | 1]) % mod; }
void pd(int i, int s, int t) {int l = (i << 1), r = (i << 1) | 1, mid = (s + t) >> 1;if (mul[i] != 1) {mul[l] *= mul[i];mul[l] %= mod;mul[r] *= mul[i];mul[r] %= mod;laz[l] *= mul[i];laz[l] %= mod;laz[r] *= mul[i];laz[r] %= mod;sum[l] *= mul[i];sum[l] %= mod;sum[r] *= mul[i];sum[r] %= mod;mul[i] = 1;}if (laz[i]) { sum[l] += laz[i] * (mid - s + 1);sum[l] %= mod;sum[r] += laz[i] * (t - mid);sum[r] %= mod;laz[l] += laz[i];laz[l] %= mod;laz[r] += laz[i];laz[r] %= mod;laz[i] = 0;}return;
}
void build(int s, int t, int i) {mul[i] = 1;if (s == t) {sum[i] = a[s];return;}int mid = s + ((t - s) >> 1);build(s, mid, i << 1);build(mid + 1, t, (i << 1) | 1);up(i);
}
void chen(int l, int r, int s, int t, int i, ll z) {int mid = s + ((t - s) >> 1);if (l <= s && t <= r) {mul[i] *= z;mul[i] %= mod;laz[i] *= z;laz[i] %= mod;sum[i] *= z;sum[i] %= mod; return;}pd(i, s, t);if (mid >= l) chen(l, r, s, mid, (i << 1), z);if (mid + 1 <= r) chen(l, r, mid + 1, t, (i << 1) | 1, z);up(i);
}
void add(int l, int r, int s, int t, int i, ll z) {int mid = s + ((t - s) >> 1);if (l <= s && t <= r) {sum[i] += z * (t - s + 1);sum[i] %= mod;laz[i] += z;laz[i] %= mod;return;}pd(i, s, t);if (mid >= l) add(l, r, s, mid, (i << 1), z);if (mid + 1 <= r) add(l, r, mid + 1, t, (i << 1) | 1, z);up(i);
}
ll getans(int l, int r, int s, int t,int i) {  int mid = s + ((t - s) >> 1);ll tot = 0;if (l <= s && t <= r) return sum[i];pd(i, s, t);if (mid >= l) tot += getans(l, r, s, mid, (i << 1));tot %= mod;if (mid + 1 <= r) tot += getans(l, r, mid + 1, t, (i << 1) | 1);return tot % mod;
}
int main() {//freopen(".in","r",stdin);//freopen(".out","w",stdout);ios::sync_with_stdio(false);cout.tie(0);int x, y, bh;ll z;n = read(), m = read(), mod = read();for(int i = 1; i <= n; i ++) a[i] = read();build(1, n, 1);for(int i = 1; i <= m; i ++) {bh = read();if(bh == 1) {x = read(), y = read(), z = read();chen(x, y, 1, n, 1, z);} else if(bh == 2) {x = read(), y = read(), z = read();add(x, y, 1, n, 1, z);} else if(bh == 3) {x = read(), y = read();cout << getans(x, y, 1, n, 1) << endl;}}return 0;
}