// Dynamic (Implicit) Segment tree: We need to create root node and create
// only those child which are required during query and update
#include<bits/stdc++.h>
using namespace std;
struct node {
node *left, *right;
int sum;
node(): left(NULL), right(NULL), sum(0) {}
void extend() {
if(!left) { // if left child does not exist, create the children
left = new node();
right = new node();
}
}
void update(int index, int updateBy, int l, int r) {
if(l == r) {
sum += updateBy; // updateBy = +1/-1vle
return;
}
extend(); // extend before accessing left and right node (extends if child does not exist)
int mid = (l+r)/2;
if(index <= mid) {
left->update(index, updateBy, l, mid);
} else {
right->update(index, updateBy, mid+1, r);
}
sum = left->sum + right->sum; // update sum of current node
}
int getSum(int qs, int qe, int l, int r) {
// if segment range is outside query range
if(r < qs || qe < l) {
return 0;
}
// if segment range is contained in query range
if(qs <=l && r <= qe) {
return sum;
}
extend();
int mid = (l+r)/2;
return left->getSum(qs, qe, l, mid) + right->getSum(qs, qe, mid+1, r);
}
};
int main() {
node* rmq = new node(); // create root node of the tree
int n, q;
cin >> n >> q;
vector<int> a(n);
for(int i=0;i<n;i++) {
cin >> a[i];
rmq->update(a[i], 1, 0, 1e9+1);
}
while(q--) {
char qt;
cin >> qt;
if(qt == '?') { //query
int a, b; cin >> a >> b;
cout << rmq->getSum(a, b, 0, 1e9+1) << "\n";
} else { //update
int k, x; cin >> k >> x;
rmq->update(a[k-1], -1, 0, 1e9+1); // decrement the sum for existing array value
rmq->update(x, 1, 0, 1e9+1); // increment the sum by 1 for new array value array value
a[k-1] = x; // update array with new value
}
}
}
Ly8gRHluYW1pYyAoSW1wbGljaXQpIFNlZ21lbnQgdHJlZTogV2UgbmVlZCB0byBjcmVhdGUgcm9vdCBub2RlIGFuZCBjcmVhdGUKLy8gb25seSB0aG9zZSBjaGlsZCB3aGljaCBhcmUgcmVxdWlyZWQgZHVyaW5nIHF1ZXJ5IGFuZCB1cGRhdGUKI2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnN0cnVjdCBub2RlIHsKICAgIG5vZGUgKmxlZnQsICpyaWdodDsKICAgIGludCBzdW07CgogICAgbm9kZSgpOiBsZWZ0KE5VTEwpLCByaWdodChOVUxMKSwgc3VtKDApIHt9CgogICAgdm9pZCBleHRlbmQoKSB7CiAgICAgICAgaWYoIWxlZnQpIHsgLy8gaWYgbGVmdCBjaGlsZCBkb2VzIG5vdCBleGlzdCwgY3JlYXRlIHRoZSBjaGlsZHJlbgogICAgICAgICAgICBsZWZ0ID0gbmV3IG5vZGUoKTsKICAgICAgICAgICAgcmlnaHQgPSBuZXcgbm9kZSgpOwogICAgICAgIH0KICAgIH0KICAgIHZvaWQgdXBkYXRlKGludCBpbmRleCwgaW50IHVwZGF0ZUJ5LCBpbnQgbCwgaW50IHIpIHsKICAgICAgICBpZihsID09IHIpIHsKICAgICAgICAgICAgc3VtICs9IHVwZGF0ZUJ5OyAvLyB1cGRhdGVCeSA9ICsxLy0xdmxlCiAgICAgICAgICAgIHJldHVybjsKICAgICAgICB9CiAgICAgICAgZXh0ZW5kKCk7IC8vIGV4dGVuZCBiZWZvcmUgYWNjZXNzaW5nIGxlZnQgYW5kIHJpZ2h0IG5vZGUgKGV4dGVuZHMgaWYgY2hpbGQgZG9lcyBub3QgZXhpc3QpCiAgICAgICAgaW50IG1pZCA9IChsK3IpLzI7CiAgICAgICAgaWYoaW5kZXggPD0gbWlkKSB7CiAgICAgICAgICAgIGxlZnQtPnVwZGF0ZShpbmRleCwgdXBkYXRlQnksIGwsIG1pZCk7CiAgICAgICAgfSBlbHNlIHsKICAgICAgICAgICAgcmlnaHQtPnVwZGF0ZShpbmRleCwgdXBkYXRlQnksIG1pZCsxLCByKTsKICAgICAgICB9CiAgICAgICAgc3VtID0gbGVmdC0+c3VtICsgcmlnaHQtPnN1bTsgLy8gdXBkYXRlIHN1bSBvZiBjdXJyZW50IG5vZGUKICAgIH0KICAgIGludCBnZXRTdW0oaW50IHFzLCBpbnQgcWUsIGludCBsLCBpbnQgcikgewogICAgICAgIC8vIGlmIHNlZ21lbnQgcmFuZ2UgaXMgb3V0c2lkZSBxdWVyeSByYW5nZQogICAgICAgIGlmKHIgPCBxcyB8fCBxZSA8IGwpIHsKICAgICAgICAgICAgcmV0dXJuIDA7CiAgICAgICAgfQogICAgICAgIC8vIGlmIHNlZ21lbnQgcmFuZ2UgaXMgY29udGFpbmVkIGluIHF1ZXJ5IHJhbmdlCiAgICAgICAgaWYocXMgPD1sICYmIHIgPD0gcWUpIHsKICAgICAgICAgICAgcmV0dXJuIHN1bTsKICAgICAgICB9CiAgICAgICAgZXh0ZW5kKCk7CiAgICAgICAgaW50IG1pZCA9IChsK3IpLzI7CiAgICAgICAgcmV0dXJuIGxlZnQtPmdldFN1bShxcywgcWUsIGwsIG1pZCkgKyByaWdodC0+Z2V0U3VtKHFzLCBxZSwgbWlkKzEsIHIpOwogICAgfQp9OwoKaW50IG1haW4oKSB7CiAgICBub2RlKiBybXEgPSBuZXcgbm9kZSgpOyAvLyBjcmVhdGUgcm9vdCBub2RlIG9mIHRoZSB0cmVlCiAgICBpbnQgbiwgcTsKICAgIGNpbiA+PiBuID4+IHE7CiAgICB2ZWN0b3I8aW50PiBhKG4pOwogICAgZm9yKGludCBpPTA7aTxuO2krKykgewogICAgICAgIGNpbiA+PiBhW2ldOwogICAgICAgIHJtcS0+dXBkYXRlKGFbaV0sIDEsIDAsIDFlOSsxKTsKICAgIH0KICAgIHdoaWxlKHEtLSkgewogICAgICAgIGNoYXIgcXQ7CiAgICAgICAgY2luID4+IHF0OwogICAgICAgIGlmKHF0ID09ICc/JykgeyAvL3F1ZXJ5CiAgICAgICAgICAgIGludCBhLCBiOyBjaW4gPj4gYSA+PiBiOwogICAgICAgICAgICBjb3V0IDw8IHJtcS0+Z2V0U3VtKGEsIGIsIDAsIDFlOSsxKSA8PCAiXG4iOwogICAgICAgIH0gZWxzZSB7IC8vdXBkYXRlCiAgICAgICAgICAgIGludCBrLCB4OyBjaW4gPj4gayA+PiB4OwogICAgICAgICAgICBybXEtPnVwZGF0ZShhW2stMV0sIC0xLCAwLCAxZTkrMSk7IC8vIGRlY3JlbWVudCB0aGUgc3VtIGZvciBleGlzdGluZyBhcnJheSB2YWx1ZQogICAgICAgICAgICBybXEtPnVwZGF0ZSh4LCAxLCAwLCAxZTkrMSk7ICAgICAgLy8gaW5jcmVtZW50IHRoZSBzdW0gYnkgMSBmb3IgbmV3IGFycmF5IHZhbHVlIGFycmF5IHZhbHVlCiAgICAgICAgICAgIGFbay0xXSA9IHg7ICAgICAgICAgICAgICAgICAgICAgIC8vIHVwZGF0ZSBhcnJheSB3aXRoIG5ldyB2YWx1ZQogICAgICAgIH0KICAgIH0KfQ==