Salary Queries

题目描述：
一家公司有 n 名员工，每名员工都有一定的薪水。你的任务是记录这些薪水并处理查询。

输入：
第一行输入两个整数 n 和 q：分别表示员工数量和查询数量。员工编号为 1、2、……、n。
接下来一行有 n 个整数 p₁、p₂、……、pₙ：表示每名员工的薪水。
之后有 q 行，每行描述一个查询，查询有以下两种形式：

• ! k x：将员工 k 的薪水改为 x
• ? a b：统计薪水在 a 到 b（包含 a 和 b）之间的员工数量

限制条件：
1 ≤ n, q ≤ 2×10⁵
1 ≤ pᵢ ≤ 10⁹
1 ≤ k ≤ n
1 ≤ x ≤ 10⁹
1 ≤ a ≤ b ≤ 10⁹

输出：
对于每个？查询，输出对应的结果。

样例输入：
5 3
3 7 2 2 5
? 2 3
! 3 6
? 2 3

样例输出：
3
2

因为x范围1-e9，全部枚举会爆，只计算可能出现的数值即可

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;int n,t,q[N][2],price[N],tree[N*6];
char sign[N];
vector<int>vals;void update(int node,int l,int r,int idx,int delta)
{if(l==r){tree[node]+=delta;return;}int mid=(l+r)>>1;if(idx<=mid)update(node*2,l,mid,idx,delta);else update(node*2+1,mid+1,r,idx,delta);tree[node]=tree[node*2]+tree[node*2+1];
}int query(int node,int l,int r,int a,int b)
{if(l>b||r<a)return 0;if(l>=a&&r<=b)return tree[node];int mid=(l+r)>>1;return query(node*2,l,mid,a,b)+query(node*2+1,mid+1,r,a,b);
}int get_idx(int x)
{return lower_bound(vals.begin(),vals.end(),x)+1-vals.begin();
}int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);set<int>all;vector<int>a;cin>>n>>t;for(int i=1;i<=n;++i){cin>>price[i];all.insert(price[i]);}for(int i=0;i<t;++i){cin>>sign[i]>>q[i][0]>>q[i][1];if(sign[i]=='!')all.insert(q[i][1]);}vals.assign(all.begin(),all.end());int m=vals.size();for(int i=1;i<=n;++i){int idx=get_idx(price[i]);update(1,1,m,idx,1);} for(int i=0;i<t;++i){if(sign[i]=='!'){int k=q[i][0];int x=q[i][1];int idx;idx=get_idx(price[k]);price[k]=x;update(1,1,m,idx,-1);idx=get_idx(x);update(1,1,m,idx,1);}else{int a=q[i][0];int b=q[i][1];int idx1=get_idx(a);int idx2=upper_bound(vals.begin(),vals.end(),b)-vals.begin();cout<<query(1,1,m,idx1,idx2)<<'\n';}}return 0;
}