不需要build , 后面调用 update就行了,
问题2 :
每次查询离散化位置都要调用 gd() , 这样也很慢哦 , 因为离散以后 ,位置是固定的, 可以查询后,存储好查询结果 , 分享一下标程的写法
auto I = [&](int x) {
return upper_bound(v.begin(), v.end(), x) - v.begin();
};
for()
a[i] = I(a[i]);
这样a[i]被赋值后就存储了离散数组中对应的位置.
对应后续的操作
if (c == '!') { //修改操作
upd(a[x], -1); //原有的值 , 不需要重新二分查询
upd(a[x] = I(y), 1); //新值, 需要查询位置
} else cout << query(I(x), I(y)) << endl; // 可能都是新值, 所以需要调用`I()`