【模板】cdq分治代替树状数组（单点修改，区间查询）

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <queue>

using namespace std;

const int N = (int)1e6 + 5;

int n, m;

struct Q{

	int type, id;

	long long val;

	friend bool operator < (Q x, Q y){

	    return x.id == y.id ? x.type < y.type : x.id < y.id;

	}

}q[N], tmp[N];

int qsize;

long long ans[N];

int asize;

void cdq(int l, int r){//左闭右开

	if(r - l <= 1) return ;//长度为1的区间内部就不会有贡献了

	int mid = l + ((r - l) >> 1);

	cdq(l, mid); cdq(mid, r);

	long long sum = 0;

	int i = l, j = mid, tsize = 0;

        //合并并计算左区间对右区间贡献

	while(i < mid && j < r){

		if(q[i] < q[j]){

			if(q[i].type == 1) sum += q[i].val;

			tmp[++tsize] = q[i++];

		}

		else {

			if(q[j].type == 2) ans[q[j].val] -= sum;

			else if(q[j].type == 3) ans[q[j].val] += sum;

			tmp[++tsize] = q[j++];

		}

	}

	while(i < mid) tmp[++tsize] = q[i++];

	while(j < r){

		if(q[j].type == 2) ans[q[j].val] -= sum;

		else if(q[j].type == 3) ans[q[j].val] += sum;

		tmp[++tsize] = q[j++];

	}

	for(int i = 1; i <= tsize; ++i) q[l + i - 1] = tmp[i];

}

/*

这部分的思路总结

判断是否到边界

下方左右分治

计算左边对右边的贡献

把左右类似归并排序重排

*/

int main() {

	scanf("%d%d", &n, &m);

	for(int i = 1; i <= n; ++i){

		++qsize;

		q[qsize].id = i, q[qsize].type = 1;

		scanf("%lld", &q[qsize].val);

	}

	for(int i = 1; i <= m; ++i){

		scanf("%d", &q[++qsize].type);

		if(q[qsize].type == 1){

			scanf("%d%lld", &q[qsize].id, &q[qsize].val);

		}

		else {

			int l, r; scanf("%d%d", &l, &r);

			++asize;

			q[qsize].id = l - 1, q[qsize].val = asize;

			q[++qsize].id = r, q[qsize].type = 3, q[qsize].val = asize;

		}

	}

	cdq(1, qsize + 1);

	for(int i = 1; i <= asize; ++i) printf("%lld\n", ans[i]);

	return 0;

}
巴特西

【模板】cdq分治代替树状数组（单点修改，区间查询）

最新文章

热门文章
