简单分块(
作者:
春江花月夜ovo
,
2024-05-05 23:36:07
,
所有人可见
,
阅读 29
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 1e5 + 10;
const int M = 370;
int n, m;
ll sum[M];
ll add[M];
int w[N];
int len;
int get(int x)
{
return (x - 1) / len;
}
void change(int l, int r, int d)
{
if (get(l) == get(r))
{
for (int i = l; i <= r; i ++) sum[get(i)] += d, w[i] += d;
}
else
{
int i = l, j = r;
while (get(i) == get(l)) sum[get(i)] += d, w[i] += d, i ++;
while (get(j) == get(r)) sum[get(j)] += d, w[j] += d, j --;
for (int k = get(i); k <= get(j); k ++) sum[k] += len * d, add[k] += d;
}
}
ll query(int l, int r)
{
ll ans = 0;
if (get(l) == get(r))
{
for (int i = l; i <= r; i ++) ans += w[i] + add[get(i)];
}
else
{
int i = l, j = r;
while (get(i) == get(l)) ans += w[i] + add[get(i)], i ++;
while (get(j) == get(r)) ans += w[j] + add[get(j)], j --;
for (int k = get(i); k <= get(j); k ++) ans += sum[k];
}
return ans;
}
int main()
{
ios::sync_with_stdio(false), cin.tie(0);
cin >> n >> m;
len = sqrt(n);
for (int i = 1; i <= n; i ++) cin >> w[i], sum[get(i)] += w[i];
int l, r, d;
char op;
while (m --)
{
cin >> op >> l >> r;
if (op == 'C')
{
cin >> d;
change(l, r, d);
}
else cout << query(l, r) << "\n";
}
return 0;
}