i dont know where im wrong, using fenwick and sqrt decom
it just get wa in test 3 so i dont think my strategy wrong or anything like that
pls give me any idea, thank u very much
here my code
include <bits/stdc++.h>
using namespace std;
define int long long
using ull = unsigned long long;
const int bs = 331;
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i] ;
vector<pair<int, int>> pr(n);
for (int i = 0; i < n; i++) {
cin >> pr[i].first >> pr[i].second;
}
int q;
cin >> q;
vector bit(n + 1);
for (int i = 1; i <= n; i++) bit[i] = a[i];
for (int i = 1; i <= n; i++) {
int j = i + (i & (-i));
if (j <= n) bit[j]+=bit[i];
}
auto update =[&](int idx, ull newval) {
ull oldval = a[idx];
a[idx] = newval;
while (idx <= n) {
if (newval >= oldval) bit[idx] += (newval - oldval);
else bit[idx] -= (oldval - newval);
idx = idx + (idx & (-idx));
}
};
auto get = [&](int idx) {
int sum = 0;
while (idx > 0) {
sum+=bit[idx];
idx = idx - (idx & (-idx));
}
return sum;
};
vector f(n);
for (int i = 0; i < n; i++) {
f[i] = get(pr[i].second) - get(pr[i].first - 1);
}
int nob = n/bs ;
vector<vector<uint16_t>> cnt(nob + 1, vector<uint16_t>(n + 2, 0));
vector sum(nob + 1);
for (int i = 0; i <= nob; i++) {
int l = i*bs;
int r = min(n - 1, (i + 1)bs - 1);
for (int j = l; j <= r; j++) {
sum[i]+=(get(pr[j].second) - get(pr[j].first - 1));
++cnt[i][pr[j].first];
–cnt[i][pr[j].second + 1];
}
for (int j = 1; j <= n; j++) cnt[i][j]+=cnt[i][j-1];
}
for (int i = 1; i <= q; i++) {
int type, u, v;
cin >> type >> u >> v;
if (type == 1) {
for (int j = 0; j <= nob; j++) sum[j]+=cnt[j][u](v - a[u]);
update(u, v);
}
else {
int bl = (u - 1)/bs;
int br = (v - 1)/bs;
int ans = 0;
if (bl == br) {
for (int j = u - 1; j <= v - 1; j++) {
ans+=(get(pr[j].second) - get(pr[j].first - 1));
}
}
else {
for (int j = bl + 1; j <= br - 1; j++) ans+=sum[j];
for (int j = u - 1; j < (bl + 1)bs; j++) {
ans+=(get(pr[j].second) - get(pr[j].first - 1));
}
for (int j = brbs; j <= v - 1; j++) {
ans+=(get(pr[j].second) - get(pr[j].first - 1));
}
}
cout << ans << ‘\n’;
}
}
return 0;
}