5.数列分块入门 5

😊 | Powered By HeartFireY | 分块例题

#6281. 数列分块入门 5 - 题目 - LibreOJ (loj.ac)

给出一个长为 n n n的数列，以及 n n n个操作，操作涉及区间开方，区间求和。

首先明确对于开方操作，不满足区间可加性，因此无法对整个分块直接开方。

考虑如何优化开方操作：不难发现对于任意元素，在经过有限次开方向下取整后一定会变为 1 1 1。同理对于某个分块，在有限次开方后也会变为 1 1 1。因此我们维护一个标记，表示当前块是否全部为 1 1 1，如果全部为 1 1 1则跳过开方操作。

对于不完整块，每次更新时仍然采取暴力更新操作即可。

#include 
#define ll long long
using namespace std;

const int N = 5e5 + 10;
int id[N], blo;
ll a[N], sum[N], tag[N];

inline void update(int ID, int loc){
    sum[id[ID]] -= a[loc], a[loc] = sqrt(a[loc]), sum[id[ID]] += a[loc];
}


void Sqrt(int l, int r){
    for(int i = l; i > r >> v;
        if(op == 0) Sqrt(l, r);
        else cout