制作静态网站制作,wordpress多语言包,淮北市建设协会网站,网络服务推广题意简述 已知一个数列#xff0c;你需要进行下面两种操作#xff1a; 1.将某区间每一个数加上x 2.求出某区间每一个数的和 题解思路 对于一个长度为n的序列#xff0c;我们可以讲其中的元素分为\( \sqrt{n} \) 个连续的子序列#xff0c;每块的长度自然就为\( \sqrt{n} \)… 题意简述 已知一个数列你需要进行下面两种操作 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;
} 转载于:https://www.cnblogs.com/xuyixuan/p/9429524.html
