40pts求助
  • 板块P4868 Preprefix sum
  • 楼主nofe
  • 当前回复0
  • 已保存回复0
  • 发布时间2022/11/14 23:08
  • 上次更新2023/10/27 02:55:42
查看原帖
40pts求助
309555
nofe楼主2022/11/14 23:08

反复检查了好几遍都没有发现问题

#include <iostream>
#include <string>

using namespace std;

constexpr const int maxn = 1e6 + 10;
int n, m, t1, t2, x, y;
long long c1[maxn], c2[maxn], in[maxn];
string inp;

auto lowbit(int x) -> int {
    return x & -x;
}

auto add1(int x, int k) -> void {
    while(x <= n) {
        c1[x] += k;
        x += lowbit(x);
    }
}
auto add2(int x, int k) -> void {
    while(x <= n) {
        c2[x] += k;
        x += lowbit(x);
    }
}

auto query1(int x) -> int {
    int ans = 0;
    while(x > 0) {
        ans += c1[x];
        x -= lowbit(x);
    }
    return ans;
}
auto query2(int x) -> int {
    int ans = 0;
    while(x > 0) {
        ans += c2[x];
        x -= lowbit(x);
    }
    return ans;
}

auto main() -> int {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> t1;
        in[i] = t1;
        add1(i, t1);
        add2(i, t1 * i);
    }
    t1 = 0, t2 = 0;
    for(int i = 0; i < m; i++) {
        cin >> inp;
        if(inp == "Query") {
            cin >> x;
            cout << (x + 1) * query1(x) - query2(x) << endl;
        } else {
			cin >> x >> y;
			add1(x, (y - in[x]));
			add2(x, (y - in[x]) * x);
			in[x] = y;
        }
    }
    return 0;
}

2022/11/14 23:08
加载中...