可以做动画的网站都有哪些,潍坊高级网站建设推广,网站建设前期,小程序商城哪的服务好速度即转发
给定一个长度为nnn的数组aaa#xff0c;里面元素为a1,a2,a3,…,an−1,ana_1, a_2, a_3, \dots, a_{n - 1}, a_na1,a2,a3,…,an−1,an。
有两种操作#xff1a;
修改apka_p kapk。给定l,r,kl, r, kl,r,k#xff0c;设S(x)∑ilrmax(ai−x,0)S(x) …速度即转发
给定一个长度为nnn的数组aaa里面元素为a1,a2,a3,…,an−1,ana_1, a_2, a_3, \dots, a_{n - 1}, a_na1,a2,a3,…,an−1,an。
有两种操作
修改apka_p kapk。给定l,r,kl, r, kl,r,k设S(x)∑ilrmax(ai−x,0)S(x) \sum\limits_{i l} ^{r} max(a_i - x, 0)S(x)il∑rmax(ai−x,0)求x∈[0,105]x \in[0, 10 ^ 5]x∈[0,105]内满足S(x)≥kS(x) \geq kS(x)≥k的最大整数xxx。
保证任何时刻数组值域在[0,105][0, 10 ^ 5][0,105]对于查询操作0≤k≤1050 \leq k \leq 10 ^ 50≤k≤105。
有个简单的想法树状数组套主席树对于操作一直接修改即可O(log2n)O(\log ^ 2 n)O(log2n)对于操作二二分答案O(log3n)O(\log ^ 3 n)O(log3n)
显然三个log\loglog的算法复杂度有点大可能过不了考虑在线段树上二分答案
假设我们当前所在的区间是[l,r][l, r][l,r]显然左子树代表的值域范围是[l,mid][l, mid][l,mid]右子树所代表的是[mid1,r][mid 1, r][mid1,r]
如果答案在右子树则答案最少为mid1mid 1mid1这个时候只要判断是否有ls_sum−sz_ls×(mid1)≥kls\_sum - sz\_ls \times (mid 1) \geq kls_sum−sz_ls×(mid1)≥k即可
如果成立则说明答案最少为mid1mid 1mid1我们可以进入右子树搜索否则我们进入右子树搜索最后我们到达的叶节点即为最优的答案
我们在递归的时候两个变量upper_sum,upper_szupper\_sum, upper\_szupper_sum,upper_sz当我们进入左子树的时候把右子树的sum,szsum, szsum,sz同时累加到这两个变量上去
由于我们往左子树走了说明答案小于mid1mid 1mid1了右子树记录的信息都是≥mid1\geq mid 1≥mid1的 在下一步的judgejudgejudge中我们可以直接使用右子树的信息。
#include bits/stdc.husing 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;
}
