题意简述
已知一个数列, 你需要进行下面两种操作:
1. 将某区间每一个数加上 x
2. 求出某区间每一个数的和
题解思路
对于一个长度为 n 的序列, 我们可以讲其中的元素分为 $ \sqrt{n}\(个连续的子序列, 每块的长度自然就为 \) \sqrt{n}$.
我们更新一段区间 [l,r], 可以先更新 l 到 l 所在块的右端点, r 到 r 所在块的右端点到 r 和中间的整个区间.
代码
- #include <cmath>
- #include <cstdio>
- using namespace std;
- typedef long long ll;
- struct Point{
- ll w, num;
- };
- struct K{
- ll l, r, tot, sum;
- ll len()
- {
- return r - l + 1;
- }
- };
- ll n, m, s, len;
- Point p[100001];
- K k[501];
- void add(ll x, ll y, ll t)
- {
- if (p[x].num == p[y].num)
- {
- for (register ll i = x; i <= y; ++i)
- p[i].w += t;
- k[p[x].num].tot += (y - x + 1) * t;
- return;
- }
- for (register ll i = x; i <= k[p[x].num].r; ++i)
- p[i].w += t;
- k[p[x].num].tot += (k[p[x].num].r - x + 1) * t;
- for (register ll i = k[p[y].num].l; i <= y; ++i)
- p[i].w += t;
- k[p[y].num].tot += (y - k[p[y].num].l + 1) * t;
- for (register ll i = p[x].num + 1; i <= p[y].num - 1; ++i)
- {
- k[i].tot += t * k[i].len();
- k[i].sum += t;
- }
- }
- ll query(ll x, ll y)
- {
- ll ans = 0;
- if (p[x].num == p[y].num)
- {
- for (register ll i = x; i <= y; ++i)
- ans += p[i].w;
- return ans;
- }
- for (register ll i = x; i <= k[p[x].num].r; ++i)
- ans += p[i].w + k[p[x].num].sum;
- for (register ll i = k[p[y].num].l; i <= y; ++i)
- ans += p[i].w + k[p[y].num].sum;
- for (register ll i = p[x].num + 1; i <= p[y].num - 1; ++i)
- ans += k[i].tot;
- return ans;
- }
- int main()
- {
- scanf("%lld%lld", &n, &m);
- len = sqrt(n);
- s = n / len + (bool)(n % len);
- for (register ll i = 1; i <= s; ++i)
- {
- k[i].l = (i - 1) * len + 1;
- k[i].r = i * len;
- }
- k[s].r = n;
- for (register ll i = 1; i <= n; ++i)
- {
- scanf("%lld", &p[i].w);
- p[i].num = (i - 1) / len + 1;
- k[p[i].num].tot += p[i].w;
- }
- for (register ll i = 1; i <= m; ++i)
- {
- ll op, x, y, t;
- scanf("%lld", &op);
- if (op == 1)
- {
- scanf("%lld%lld%lld", &x, &y, &t);
- add(x, y, t);
- }
- else
- {
- scanf("%lld%lld", &x, &y);
- printf("%lld\n", query(x, y));
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2716445.html