B. The Tortoise and the Hare

給定一個長度為$n$的數組$a,(1\le a_i<m)$，$m$是一個給定的數$(1\le m\le 10^9)$，有$Q$次操作，分為兩類：

• 給定$u,v,(1\le u\le n,1\le v<m)$，把數組上$a_u$的值改為$v$。
• 給定$l,r,k,(1\le l\le r\le n,1\le k\le r?l)$，每次對$[l,r]$區間內前$r?l+1?k$小的數都$+1$，問最多能進行多少次操作， 使得$i\in [l,r],a_i<m$恒成立。

對于操作一，我們直接修改即可，如何計算詢問二呢，我們思考如下一個問題:

給定一個長度為$n$的數組$a$，每次我們要選擇$k$個不同的數，把這$k$個數的值都減$1$，問我們最多能進行幾次操作。

這個問題考慮最優解法，其實就是每次拿前$k$大，然后對這$k$個數都減$1$，知道不能進行操作為止。

不難發現其實這個問題，跟我們的詢問二操作是幾乎一樣的，如果我們對詢問二中的每個$a_i$都存$m?a_i?1$的值，這個問題就變得跟上述問題是一樣的了。

考慮如何快速解決這個問題（因為我們不能對每次詢問都進行模擬），嘗試二分求解：

假設我們當前二分區間為$[l,r]$，判斷答案是在$[l,mid]$或者$[mid+1,r]$區間，所以我們需要判斷$x=mid+1$是否是可行的。

對于那些$a_i\ge x$的數來說，如果每次刪除我們都選他，可以發現對整個過程的模擬是沒有影響的，假設這樣的數有$cnt$個。

接下來我們的問題就轉換成為，當所有數都$<x$，我們每次需要挑選$k?cnt$個數然后對其$?1$，能否進行$x$次操作了。

我們再對這個問題進行轉換，如果我們要進行$x$次操作，每次我們最多能選多少個數，如果每次可選的數$\ge k?cnt$，則說明合法。

由于$a_i<x$，我們進行了$x$次操作，說明，我們可以滿足在同一次操作中不會出現兩個一樣的，所以每次可選的數為$\frac{sum}{x}$。

由此我們解決了，詢問操作，如果是靜態問題，可以考慮直接主席樹上二分，但是這里是一個帶修的問題，所以可以考慮樹套樹，

如果是樹狀數組套主席樹，空間復雜度將會是$O(n{\log }^{2}n)$的，不可行，所以得通過權值線段樹套平衡樹來解決，達到空間$O(n\log n)$的。

其實還有一個代碼量小，同時滿足時間復雜度的離線做法，整體二分，空間$O(n)$，時間$O(n{\log }^{2}n)$。

#include <bits/stdc++.h>using namespace std;const int N = 1e5 + 10;int n, m, T, cnt, a[N];long long ans[N];inline int lowbit(int x) {return x & (-x); }struct BIT {long long sum[N];void update(int rt, int x) {while (rt <= n) {sum[rt] += x;rt += lowbit(rt);}}long long query(int rt) {long long ans = 0;while (rt) {ans += sum[rt];rt -= lowbit(rt);}return ans;} }sum, num;struct Res {int op, id, l, r, k;/*op = 0, modify a_l + rop = 1, query [l, r], k*/long long pre_sum, pre_num;}q[N << 2], ql[N << 2], qr[N << 2];void solve(int L, int R, long long l, long long r) {if (L > R) {return ;}if (l == r) {for (int i = L; i <= R; i++) {if (!q[i].op) {ans[q[i].id] = l;}}return ;}long long mid = l + r >> 1;int cnt1 = 0, cnt2 = 0;for (int i = L; i <= R; i++) {if (q[i].op) {if (q[i].r <= mid) {sum.update(q[i].l, q[i].r * q[i].op), num.update(q[i].l, q[i].op);ql[++cnt1] = q[i];}else {qr[++cnt2] = q[i];}}else {long long pre_sum = q[i].pre_sum, pre_num = q[i].pre_num;long long cur_sum = sum.query(q[i].r) - sum.query(q[i].l - 1), cur_num = num.query(q[i].r) - num.query(q[i].l - 1);if ((q[i].r - q[i].l + 1) - pre_num - cur_num + (pre_sum + cur_sum) / (mid + 1) >= q[i].k) {q[i].pre_sum += cur_sum, q[i].pre_num += cur_num;qr[++cnt2] = q[i];}else {ql[++cnt1] = q[i];}}}for (int i = 1; i <= cnt1; i++) {if (ql[i].op) {sum.update(ql[i].l, -ql[i].r * ql[i].op), num.update(ql[i].l, -ql[i].op);}}for (int i = 1; i <= cnt1; i++) {q[L + i - 1] = ql[i];}for (int i = 1; i <= cnt2; i++) {q[L + cnt1 + i - 1] = qr[i];}solve(L, L + cnt1 - 1, l, mid);solve(L + cnt1, R, mid + 1, r); }int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);scanf("%d %d %d", &n, &m, &T);for (int i = 1; i <= n; i++) {scanf("%d", &a[i]);a[i] = m - a[i] - 1;q[++cnt] = {1, 0, i, a[i], 0, 0, 0};}for (int i = 1, op; i <= T; i++) {ans[i] = -1;scanf("%d", &op);if (op & 1) {int l, r, k;scanf("%d %d %d", &l, &r, &k);q[++cnt] = {0, i, l, r, r - l + 1 - k, 0, 0};}else {int u, v;scanf("%d %d", &u, &v);q[++cnt] = {-1, 0, u, a[u], 0, 0, 0};a[u] = m - v - 1;q[++cnt] = {1, 0, u, a[u], 0, 0, 0};}}solve(1, cnt, 0, 100000000000000);for (int i = 1; i <= T; i++) {if (ans[i] != -1) {printf("%lld\n", ans[i]);}}return 0; } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的B.The Tortoise and the Hare 长春的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。