这是我的代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, m, tot, rt[N*2], len, a[N], cnt, lsh[N * 6];
struct node {
int v, ls, rs;
} t[N * 60];
struct ll {
char opt;
int A, B, C;
} qs[N*2];
int lb(int x) {
return x & (-x);
}
void pushup(int p) {
t[p].v = t[t[p].ls].v + t[t[p].rs].v;
}
void update(int &p, int l, int r, int k, int v) {
if (!p) p = ++tot;
t[p].v += v;
if (l == r) {
return;
}
int mid = (l + r) / 2;
if (k <= mid) update(t[p].ls, l, mid, k, v);
else update(t[p].rs, mid + 1, r, k, v);
}
void add(int p, int v) {
int pos = lower_bound (lsh+1 , lsh+len+1 , a[p]) - lsh;
for (int i = p; i <= n; i += lb(i))
update(rt[i], 1, len, pos, v);
}
int query(int p, int l, int r, int k) {
if (l == r) return t[p].v;
int mid = (l + r) / 2;
if (k <= mid) return query(t[p].ls, l, mid, k);
else return query(t[p].rs, mid + 1, r, k);
}
int ask(int l, int r, int k) {
int ans = 0;
for (int i = r; i; i -= lb(i))
ans += query(rt[i], 1, len, k);
for (int i = l - 1; i; i -= lb(i))
ans -= query(rt[i], 1, len, k);
return ans;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= m; i++) {
char opt;
int A, B, K;
cin >> opt;
cin >> A >> B;
if (opt == 'C') {
lsh[++cnt] = B;
qs[i].opt = opt, qs[i].A = A, qs[i].B = B;
} else {
lsh[++cnt] = K;
cin >> K;
qs[i] = {opt, A, B, K};
}
}
sort(lsh + 1, lsh + cnt + 1);
len = unique(lsh + 1, lsh + cnt + 1) - lsh - 1;
for (int i = 1; i <= n; i++) {
add(i, 1);
}
for (int i = 1; i <= m; i++) {
if (qs[i].opt == 'C')
qs[i].B = lower_bound(lsh + 1, lsh + len + 1, qs[i].B) - lsh;
else
qs[i].C = lower_bound(lsh + 1, lsh + len + 1, qs[i].C) - lsh;
}
for (int i = 1; i <= m; i++) {
if (qs[i].opt == 'C') {
add(qs[i].A, -1);
a[qs[i].A] = qs[i].B;
add(qs[i].A, 1);
} else {
cout << ask(qs[i].A, qs[i].B, qs[i].C) << endl;
}
}
return 0;
}
提交后WA 0pts
#1的错误信息是
Wrong Answer.wrong answer On line 10 column 1, read 5, expected 6.
然而经本地测试数据点1 代码输出的第十行确实是6,而非错误信息所说的5