若找前缀和小于等于x的第一个数
整个运算过程是这样的:
从二进制的高位开始取
若当前位为1,和大于x,那么这一位就不能取1,否者当前位取1。
就这样一直判断下去,每个位置都有选或不选两种情况
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
#define int long longint n,q;
int c[N], a[N];int query(int x)
{int pos = 0, t = 0;// 就是二分的过程// 先从高位开始取,如果当前这一位可以取,那么就考虑下一位是取1还是0// 到最后找到的就是最大的那个pos并且对应的<=x的for(int j = 18; j >= 0; j --){if(pos + (1 << j) <= n && t + c[pos + (1 << j)] <= x){pos += (1 << j);t += c[pos];}}return pos;
}void modify(int x, int d)
{for(;x<=n;x+=x&(-x)) c[x] += d;
}signed main()
{cin >> n >> q;for(int i = 1; i <= n; i ++){scanf("%lld",&a[i]);modify(i, a[i]);}int op, x, d;while (q--){scanf("%lld%lld",&op,&x);if(op == 1){scanf("%lld", &d);modify(x, d - a[x]);a[x] = d;}else{printf("%lld\n", query(x));}}}
更多推荐
树状,数组
发布评论