速度即轉發

給定一個長度為$n$的數組$a$，里面元素為$a_1,a_2,a_3,\dots ,a_{n?1},a_n$。

有兩種操作：

• 修改$a_p=k$。
• 給定$l,r,k$，設$S(x)=\sum _{i=l}^{r}max(a_i?x,0)$，求$x\in [0,10^5]$內滿足$S(x)\ge k$的最大整數$x$。

保證任何時刻數組值域在$[0,10^5]$，對于查詢操作$0\le k\le 10^5$。

有個簡單的想法樹狀數組套主席樹，對于操作一，直接修改即可$O({\log }^{2}n)$，對于操作二，二分答案$O({\log }^{3}n)$，

顯然三個$\log$的算法，復雜度有點大可能過不了，考慮在線段樹上二分答案，

假設我們當前所在的區間是$[l,r]$，顯然左子樹代表的值域范圍是$[l,mid]$，右子樹所代表的是$[mid+1,r]$，

如果答案在右子樹，則答案最少為$mid+1$，這個時候只要判斷是否有$ls\_sum?sz\_ls\times (mid+1)\ge k$即可，

如果成立，則說明答案最少為$mid+1$我們可以進入右子樹搜索，否則我們進入右子樹搜索，最后我們到達的葉節點即為最優的答案

我們在遞歸的時候，兩個變量$upper\_sum,upper\_sz$，當我們進入左子樹的時候，把右子樹的$sum,sz$同時累加到這兩個變量上去，

由于我們往左子樹走了，說明答案小于$mid+1$了，右子樹記錄的信息都是$\ge mid+1$的
在下一步的$judge$中我們可以直接使用右子樹的信息。

#include <bits/stdc++.h>using namespace std;const int N = 1e5 + 10, maxn = 100000;typedef long long ll;int a[N], n, m;int root[N], ls[N << 7], rs[N << 7], num;ll sum[N << 7], sz[N << 7];inline int lowbit(int x) {return x & (-x); }void update(int &rt, int l, int r, int x, int v) {if (!rt) {rt = ++num;}sum[rt] += x * v, sz[rt] += v;if (l == r) {return ;}int mid = l + r >> 1;if (x <= mid) {update(ls[rt], l, mid, x, v);}else {update(rs[rt], mid + 1, r, x, v);} }void modify(int rt, int x, int v) {while (rt <= n) {update(root[rt], 0, maxn, x, v);rt += lowbit(rt);} }int A[110], B[110], cnt1, cnt2;int query(int l, int r, ll upper_sum, ll upper_sz, ll k) {if (l == r) {if (upper_sum - upper_sz * l >= k) {return l;}return -1;}int mid = l + r >> 1;ll cur_sum = 0, cur_sz = 0;for (int i = 1; i <= cnt1; i++) {cur_sum -= sum[rs[A[i]]], cur_sz -= sz[rs[A[i]]];}for (int i = 1; i <= cnt2; i++) {cur_sum += sum[rs[B[i]]], cur_sz += sz[rs[B[i]]];}if (cur_sum + upper_sum - 1ll * (mid + 1) * (upper_sz + cur_sz) >= k) {for (int i = 1; i <= cnt1; i++) {A[i] = rs[A[i]];}for (int i = 1; i <= cnt2; i++) {B[i] = rs[B[i]];}return query(mid + 1, r, upper_sum, upper_sz, k);}else {for (int i = 1; i <= cnt1; i++) {A[i] = ls[A[i]];}for (int i = 1; i <= cnt2; i++) {B[i] = ls[B[i]];}return query(l, mid, upper_sum + cur_sum, upper_sz + cur_sz, k);} }int get_ans(int l, int r, ll k) {cnt1 = cnt2 = 0;for (int i = l - 1; i; i -= lowbit(i)) {A[++cnt1] = root[i];}for (int i = r; i; i -= lowbit(i)) {B[++cnt2] = root[i];}return query(0, maxn, 0, 0, k); }int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);scanf("%d %d", &n, &m);for (int i = 1; i <= n; i++) {scanf("%d", &a[i]);modify(i, a[i], 1);}ll k;for (int i = 1, op, l, r, p; i <= m; i++) {scanf("%d", &op);if (op) {scanf("%d %lld", &p, &k);modify(p, a[p], -1);a[p] = k;modify(p, a[p], 1);}else {scanf("%d %d %lld", &l, &r, &k);printf("%d\n", get_ans(l, r, k));}}return 0; }

總結

以上是生活随笔為你收集整理的E速度即转发（牛客挑战赛48）（树套树）的全部內容，希望文章能夠幫你解決所遇到的問題。

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