二分快速查找修改区间,并配合差分修改

题目传送门

大致思路

依据值来修改,那么我们可以声明一个结构体:包含值和索引
结构体存储原来的索引,然后将结构体根据值来升序排序
每次修改时利用二分查找修改区间,用差分数组记录修改
所有修改结束之后,还原原数组,用ans数组存储答案

Code

struct num{
	int val;
	int index;
};

bool cmp(const struct num &a , const struct num &b ){
	return a.val < b.val;
}

void solve(){
	int n,q;
	cin >> n >> q;
	vector<num> a(n+1);
	for(int i=1;i<=n;i++) {
		a[i].index=i;
		cin >> a[i].val;
	}
	sort(a.begin()+1,a.end(),cmp);
	vector<int> d(n+2);
	vector<int> newa(n+1);
	for(int i=1;i<=n;i++) {
		newa[i]=a[i].val;
		d[i]=newa[i]-newa[i-1];
	}
	while(q--){
		int c,l,r;
		cin >> c >> l >> r;
		auto it1=lower_bound(newa.begin()+1,newa.end(),l); //第一个大于等于l的数
		auto it2 =upper_bound(newa.begin()+1,newa.end(),r)-1;//最后一个小于等于r的数
		if(it1==newa.end()) continue;
		int ll=it1-newa.begin();
		int rr;
		if(it2==newa.end()) rr=n;
		else rr=it2-newa.begin();
		if(c==1){
			d[ll]++;
			d[rr+1]--;
		}
		else {
			d[ll]--;
			d[rr+1]++;
		}
	}
	vector<int> ans(n+1);
	for(int i=1;i<=n;i++){
		newa[i]=newa[i-1]+d[i];
		ans[a[i].index]=newa[i];
	}
	for(int i=1;i<=n;i++) cout << ans[i] << " ";
	cout << endl;
}