分块开方求区间和

题目描述

给出一个长为 nn 的数列 a_1\ldots a_na1​…an​，以及 nn 个操作，操作涉及区间开方，区间求和。

输入格式

第一行输入一个数字 nn。

第二行输入 nn 个数字，第 ii 个数字为 a_iai​，以空格隔开。

接下来输入 nn 行询问，每行输入四个数字 \mathrm{opt}, l, r, copt,l,r,c，以空格隔开。

若 \mathrm{opt} = 0opt=0，表示将位于 [l, r][l,r] 的之间的数字都开方。对于区间中每个 a_i(l\le i\le r),\: a_i \leftarrow \left\lfloor \sqrt{a_i}\right\rfloorai​(l≤i≤r),ai​←⌊ai​​⌋

若 \mathrm{opt} = 1opt=1，表示询问位于 [l, r][l,r] 的所有数字的和。

输出格式

对于每次询问，输出一行一个数字表示答案。

样例

数据范围与提示

对于 100\%100% 的数据，1 \leq n \leq 50000, -2^{31} \leq \mathrm{others}1≤n≤50000,−231≤others、\mathrm{ans} \leq 2^{31}-1ans≤231−1。

#include
using namespace std;
typedef long long ll;
const int MAXN = 50010;
ll a[MAXN],block[MAXN],sum[2000],add[2000];
int st[2000],ed[2000],n,s,lazy[2000];
void init()
{s = (int)sqrt(n);int cnt = 0;for(int i = 1;i <= n; i += s){st[++cnt] = i;ed[cnt] = min(i+s-1,n);}for(int i = 1;i <= cnt; i++)for(int j = st[i];j <= ed[i]; j++)block[j] = i;
}
void modify(int x,int y)
{int l = block[x],r = block[y];if(l == r){if(lazy[l]) return;ll tmp=0;for(int i = x;i <= y; i++){ tmp += a[i]-(ll)sqrt(a[i]);a[i] = sqrt(a[i]);}sum[l] -= tmp;return;}else{ll tmp = 0;if(!lazy[l]){for(int i = x;i <= ed[l]; i++){tmp += a[i] - (ll)sqrt(a[i]);a[i] = sqrt(a[i]);}}sum[l] -= tmp;tmp = 0;if(!lazy[r]){for(int i = st[r];i <= y; i++){tmp += a[i] - (ll)sqrt(a[i]);a[i] = sqrt(a[i]); }}sum[r] -= tmp;for(int i = l+1;i }
ll query(int x,int y)
{ll ans = 0;int l = block[x],r = block[y];if(l == r){for(int i = x; i <= y; i++){ans += a[i];}}else{for(int i = x;i <= ed[l]; i++){ans += a[i];}for(int i = st[r];i <= y; i++){ans += a[i];}for(int i = l+1;i }
int main()
{ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin >> n;init();for(int i = 1;i <= n; i++){cin >> a[i];sum[block[i]] += a[i];}int opt,l,c,r;for(int i = 1;i <= n; i++){cin >> opt >> l >> r >> c;if(opt == 0) modify(l,r);else{cout <}