// 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);
}
while(q--) {
char qt;
cin >> qt;
if(qt == '?') { //query
int a, b; cin >> a >> b;
cout << rmq->getSum(a, b, 0, 1e9) << "\n";
} else { //update
int k, x; cin >> k >> x;
rmq->update(a[k-1], -1, 0, 1e9); // decrement the sum for existing array value
rmq->update(x, 1, 0, 1e9); // 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+dXBkYXRlKGFbaV0sIDEsIDAsIDFlOSk7CiAgICB9CiAgICB3aGlsZShxLS0pIHsKICAgICAgICBjaGFyIHF0OwogICAgICAgIGNpbiA+PiBxdDsKICAgICAgICBpZihxdCA9PSAnPycpIHsgLy9xdWVyeQogICAgICAgICAgICBpbnQgYSwgYjsgY2luID4+IGEgPj4gYjsKICAgICAgICAgICAgY291dCA8PCBybXEtPmdldFN1bShhLCBiLCAwLCAxZTkpIDw8ICJcbiI7CiAgICAgICAgfSBlbHNlIHsgLy91cGRhdGUKICAgICAgICAgICAgaW50IGssIHg7IGNpbiA+PiBrID4+IHg7CiAgICAgICAgICAgIHJtcS0+dXBkYXRlKGFbay0xXSwgLTEsIDAsIDFlOSk7IC8vIGRlY3JlbWVudCB0aGUgc3VtIGZvciBleGlzdGluZyBhcnJheSB2YWx1ZQogICAgICAgICAgICBybXEtPnVwZGF0ZSh4LCAxLCAwLCAxZTkpOyAgICAgIC8vIGluY3JlbWVudCB0aGUgc3VtIGJ5IDEgZm9yIG5ldyBhcnJheSB2YWx1ZSBhcnJheSB2YWx1ZQogICAgICAgICAgICBhW2stMV0gPSB4OyAgICAgICAgICAgICAgICAgICAgICAvLyB1cGRhdGUgYXJyYXkgd2l0aCBuZXcgdmFsdWUKICAgICAgICB9CiAgICB9Cn0=