POJ 3468 A Simple Problem with Integers (分块解法)

缺乏、安全感 2021-12-15 11:09 206阅读 0赞

## 题意: 输入 n, m表初始有 n 个数, 接下来 m 行输入, Q x y 表示询问区间 \[x, y\]的和； ##

## C x y z 表示区间 \[x, y\] 内所有数加上 z 。 ##

## 分析: ##

## 我们将所给序列分成一个一个大小为根号n的块，每次询问时在线处理： ##

## 额外用到的数组： ##

## pos\[maxn\]：pos\[i\]表示第i个元素属于哪个块。 ##

## add\[maxn\]:add\[i\]表示第i个块的增量。 ##

## sum\[maxn\]:sum\[i\]表示第i个块的总和。 ##

## L\[maxn\]:L\[i\]表示第i个块的左端点。 ##

## R\[maxn\]:R\[i\]表示第i个块的右端点。 ##

## 一·询问操作  Q l r ： ##

## 1.如果l和r都在一个块内，直接利用朴素算法从a\[l\]加到a\[r\]。 ##

## 2.如果不一样，我们令p=pos\[l\],q=pos\[r\],l和r之间完整的块为从p+1到q-1，所以我们累加sum\[i\]+add\*(R\[i\]-L\[i\]+1),i从p+1到q-1。 ##

## 之后我们对于不完整的两端进行朴素处理。 ##

## 二·改变操作 C l r val: ##

## 1.如果l和r都在一个块内，直接利用朴素算法从a\[l\]改变到a\[r\]。 ##

## 2.如果不一样，我们令p=pos\[l\],q=pos\[r\],l和r之间完整的块为从p+1到q-1，所以我们改变add\[i\]+=val,i从p+1到q-1。 ##

## 之后我们对于不完整的两端进行朴素处理。 ##

## 总复杂度为O((N+M)\*√N)。 ##

## 代码: ##

//参考《算法竞赛进阶指南》
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<cmath>
    using namespace std;
    long long a[100010], sum[100010], add[100010];
    int L[100010], R[100010]; // 每段左右端点
    int pos[100010]; // 每个位置属于哪一段
    int n, m, t;
    
    void change(int l, int r, long long d) {
    	int p = pos[l], q = pos[r];
    	if (p == q) {
    		for (int i = l; i <= r; i++) a[i] += d;
    		sum[p] += d*(r - l + 1);
    	}
    	else {
    		for (int i = p + 1; i <= q - 1; i++) add[i] += d;
    		for (int i = l; i <= R[p]; i++) a[i] += d;
    		sum[p] += d*(R[p] - l + 1);
    		for (int i = L[q]; i <= r; i++) a[i] += d;
    		sum[q] += d*(r - L[q] + 1);
    	}
    }
    
    long long ask(int l, int r) {
    	int p = pos[l], q = pos[r];
    	long long ans = 0;
    	if (p == q) {
    		for (int i = l; i <= r; i++) ans += a[i];
    		ans += add[p] * (r - l + 1);
    	}
    	else {
    		for (int i = p + 1; i <= q - 1; i++)
    			ans += sum[i] + add[i] * (R[i] - L[i] + 1);
    		for (int i = l; i <= R[p]; i++) ans += a[i];
    		ans += add[p] * (R[p] - l + 1);
    		for (int i = L[q]; i <= r; i++) ans += a[i];
    		ans += add[q] * (r - L[q] + 1);
    	}
    	return ans;
    }
    
    int main() {
    	cin >> n >> m;
    	for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    	// 分块
    	t = sqrt(n*1.0);
    	for (int i = 1; i <= t; i++) {
    		L[i] = (i - 1)*sqrt(n*1.0) + 1;
    		R[i] = i*sqrt(n*1.0);
    	}
    	if (R[t] < n) t++, L[t] = R[t - 1] + 1, R[t] = n;
    	// 预处理
    	for (int i = 1; i <= t; i++)
    		for (int j = L[i]; j <= R[i]; j++) {
    			pos[j] = i;
    			sum[i] += a[j];
    		}
    	// 指令
    	while (m--) {
    		char op[3];
    		int l, r, d;
    		scanf("%s%d%d", op, &l, &r);
    		if (op[0] == 'C') {
    			scanf("%d", &d);
    			change(l, r, d);
    		}
    		else printf("%lld\n", ask(l, r));
    	}
    }