有帮助的题集第三篇 😃😃😃。
题意
有 $n$ 个人喜欢看电影，第 $i$ 个人对电影的评价有两个，动作元素值 $a_i$ 和剧情元素值 $d_i$。现在有一部电影的上述两个值为 $ac$ 和 $dr$，每个人要满足一个条件 TA 才会去看这部电影。具体为：设电影的流行度 \(P\) 为已经观看了这部电影的人数，若第 \(i\) 个人满足 \(\max(a_i-ac,0)+\max(d_i-dr,0)\le P\)，则 TA 不论如何都一定会去看该电影。
当一个人看了这部电影后，流行度 \(P\) 就会加 \(1\)。于是可能更多的人就会去看这部电影。不过每个人的喜好是随时会变的，有 \(m\) 个变化事件，每个变化中第 \(k\) 个用户的动作元素值和剧情元素值会分别变成 \(na\) 和 \(nd\)。对于每个变化，你需要重新计算电影最终的流行度 \(P\)。
Hint 1
令 $p_i$ 表示每个人看电影的最低标准，那么 $p_i=\max(a_i-ac,0)+\max(d_i-dr,0)$。对于每一种确定的状态，最终的流行度 $P$ 满足什么？Hint 2
Solution
首先，如果要让 $P$ 增长到 $k$，那么需要满足的条件是至少 $k$ 个人的 $p_iCode
#include <bits/stdc++.h>
#define loop(i,a,b) for(int i=(a);~i;i=(b))
#define eb emplace_back
#define pb push_back
#define print(x,c) write(x),putchar(c),flush()
using namespace std;
typedef long long ll;
constexpr int N = 5e5 + 15;namespace FAST_IO {
#define IOSIZE 300000char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)template <typename T> inline void read (T &x) { x = 0; T f = 1;char ch = getchar ();while (!isdigit (ch)) {if (ch == '-') f = -1; ch = getchar ();}while (isdigit (ch)) {x = (x << 1) + (x << 3) + (ch ^ '0'); ch = getchar ();} x *= f;}template <> inline void read (double &x) { x = 0; int f = 1;char ch = getchar ();while (!isdigit (ch)) { if (ch == '-') f = -1; ch = getchar ();} while (isdigit (ch)) x = x * 10 + (ch - '0'), ch = getchar ();if (ch == '.') {ch = getchar (); for (double t = 0.1; isdigit (ch); t *= 0.1) x += t * (ch - '0'), ch = getchar ();}x *= f;}inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }template <typename T, typename ...Args> inline void read (T &x, Args &...args) {read(x); read(args...);}template <typename T> inline void write (T x) { if (x < 0) putchar ('-'), x = -x; if (x > 9) write (x / 10); putchar (x % 10 + 48);}inline void write(char *x) { while (*x) putchar(*x++); }inline void write(const char *x) { while (*x) putchar(*x++); }inline void flush() { if (p3 != obuf) { fwrite(obuf, 1, p3 - obuf, stdout);p3 = obuf;}}
}
using namespace FAST_IO;int ac, dr;
int n;
int a[N], d[N];
int m;
struct tree {int l, r;ll v, f;
}tr[N << 3];void push_up (int u) {tr[u].v = min (tr[u << 1].v, tr[u << 1 | 1].v);
}void push_down (int u) {if (tr[u].f) {tr[u << 1].f += tr[u].f;tr[u << 1 | 1].f += tr[u].f;tr[u << 1].v += tr[u].f;tr[u << 1 | 1].v += tr[u].f;tr[u].f = 0;}
}void build (int u, int l, int r) {tr[u].l = l, tr[u].r = r;if (l == r) {tr[u].v = -l;return ;}int mid = l + r >> 1;build (u << 1, l, mid);build (u << 1 | 1, mid + 1, r);push_up (u);
}void update (int u, int l, int r, ll v) {if (tr[u].l >= l && tr[u].r <= r) {tr[u].f += v;tr[u].v += v;return ;}push_down (u);int mid = tr[u].l + tr[u].r >> 1;if (l <= mid) update (u << 1, l, r, v);if (r > mid) update (u << 1 | 1, l, r, v);push_up (u);
}ll query (int u) {if (tr[u].l == tr[u].r) {return tr[u].l;}push_down (u);int mid = tr[u].l + tr[u].r >> 1;ll ans = -1;if (tr[u << 1].v < 0) ans = query (u << 1);else ans = query (u << 1 | 1);return ans;
}int main () {read (ac, dr, n);for (int i = 1; i <= n; ++ i) read (a[i]);for (int i = 1; i <= n; ++ i) read (d[i]);build (1, 1, n + 2);for (int i = 1; i <= n; ++ i) {int pos = min (n, max (a[i] - ac, 0) + max (d[i] - dr, 0));update (1, pos + 1, n + 2, 1);}read (m);while (m --) {int k, na, nd;read (k, na, nd);int pos = min (n, max (a[k] - ac, 0) + max (d[k] - dr, 0));update (1, pos + 1, n + 2, -1);a[k] = na, d[k] = nd;pos = min (n, max (a[k] - ac, 0) + max (d[k] - dr, 0));update (1, pos + 1, n + 2, 1);print (query (1) - 1, '\n');}return 0;
}
题外话
今年目标：