数列分块

题目链接：https://loj.ac/p/6281

题目描述

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

输入格式

第一行输入一个数字n 。

第二行输入n个数字，第i个数字为$$a_{i}$$，以空格隔开。

接下来输入n行询问，每行输入四个数字opt，l，r，c，以空格隔开。

若opt = 0，表示将位于[l,r]的之间的数字都开方。对于区间中每个$$a_{i}(l \leq i \leq r)$$

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

输出格式

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

样例

输入复制
4
1 2 2 3
0 1 3 1
1 1 4 4
0 1 2 2
1 1 2 4
输出复制
6
2

数据范围与提示

对于 $$100%$$的数据，$$1\leq n \leq 50000,-2^{31}\leq others、ans \leq 2^{31}-1$$

分析

这题数列分块的难点在于每次操作是对区间内的每个数字进行开方操作，但是题目要求是下取整开方，那么所有数字经过若干次开方，最后的结果一定是1或者0，所以只要判断某些完整的块是否为0或为1，为0或1就跳过

变量：

blo：表示每块的元素个数 
block：用来记录每个元素对应下标所属的块号
sum：用来记录每个块的和
a：用来存储数据 
vis[maxn]：标记是否存在整块和为0或1的块
block[i]*blo：块i对应的最大下标

更新操作：

三段更新：

第一段：

从 $$l$$ 开始到 $$l$$ 所属的块结束

区间：$$[l,min(block[l]*blo,r)]$$

第二段：

当 $$l$$ 和 $$r$$ 属于不同的块时，前面更新完第一段以后，第二段更新要从$$ r $$所在块的第一个元素开始，直到$$r$$结束

区间：$$[(block[r]-1)*blo+1,r]$$

第三段：

判断是否存在一个完整的块，该块的和为0或者1，如果满足和为0或1就对他进行标记，下次更新操作时直接跳过该块。

void update(int l,int r){
    /**
        更新l到右侧的最小值端点,
        block[l]*blo表示l所在块的最大下标
        取 block[l]*blo与r二者中最小的元素，更新该区间 
    **/
    for(int i = l ; i <= min(r,block[l]*blo) ; i++){
        if(vis[block[l]]) break;
        sum[block[l]] -= a[i];
        a[i] = sqrt(a[i]);
        sum[block[l]] += a[i];
    }
    if(block[l] != block[r]){
        /**
        如果 block[l] != block[r]说明存在部分元素在r所属的块内
        那么更新block[i]内的元素，到r截止，所以更新区间[(block[r]-1)*blo+1,r] 
        **/
        for(int i = (block[r]-1)*blo+1 ; i <= r ; i++){
            if(vis[block[r]]) break;
            sum[block[r]] -= a[i];
            a[i] = sqrt(a[i]);
            sum[block[r]] += a[i];
        }
    }
    //这里从block[l]+1开始是因为要寻找完整的块 
    for(int i = block[l]+1 ; i <= block[r]-1 ; i++) visSqrt(i);
}

标记操作：

x表示块号

（1）如果该块已经被标记就直接return。

（2）如果没有被标记，就判断该块的和是否大于1，如果大于1就不需要被标记，否则标记为true

void visSqrt(int x){
    if(vis[x]) return;
    vis[x] = true;
    sum[x] = 0;
    for(int i = (x-1)*blo + 1 ; i <= x*blo ; i++){
        a[i] = sqrt(a[i]);
        sum[x] += a[i];
        if(a[i] > 1){
            vis[x] = false;
        }
    }
}

查询操作：

三段查询：

第一段：

从 $$l$$ 开始到 $$l$$ 所属的块结束

区间：$$[l,min(block[l]*blo, r)]$$

第二段：

当 $$l$$ 和 $$r$$ 属于不同的块时，前端计算完第一段的和之后，第二段的和要从 $$ r $$ 所在块的第一个元素开始，直到 $$r$$ 结束

区间：$$[(block[r]-1)*blo+1,r]$$

第三段：

由于在更新操作中，对某些块和为0或1的块进行标记并且跳过，所以在查询的最后一段，要加上原来跳过的块的和

int query(int l,int r){
    int ans = 0;
    for(int i = l ; i <= min(r,block[l]*blo) ; i++) ans += a[i];
    if(block[l] != block[r]){
        for(int i = (block[r]-1)*blo+1 ; i <= r ; i++) ans += a[i];
    }
    for(int i = block[l] + 1 ; i <= block[r]-1 ; i++) ans += sum[i];
    return ans;
}

AC代码：

#include

using namespace std;

const int maxn = 5e4+5;


int n,blo;//blo表示每块的元素个数 
int block[maxn],sum[maxn],a[maxn];//block用来记录，每个元素对应下标所属的块号，sum用来记录每个块的和，a用来存储数据 
bool vis[maxn]; //标记是否存在整块和为0或1的块 

void visSqrt(int x){
    if(vis[x]) return;
    vis[x] = true;
    sum[x] = 0;
    for(int i = (x-1)*blo + 1 ; i <= x*blo ; i++){
        a[i] = sqrt(a[i]);
        sum[x] += a[i];
        if(a[i] > 1){
            vis[x] = false;
        }
    }
}

void update(int l,int r){
    /**
        更新l到右侧的最小值端点,
        block[l]*blo表示l所在块的最大下标
        取 block[l]*blo与r二者中最小的元素，更新该区间 
    **/
    for(int i = l ; i <= min(r,block[l]*blo) ; i++){
        if(vis[block[l]]) break;
        sum[block[l]] -= a[i];
        a[i] = sqrt(a[i]);
        sum[block[l]] += a[i];
    }
    if(block[l] != block[r]){
        /**
        如果 block[l] != block[r]说明存在部分元素在r所属的块内
        那么更新block[i]内的元素，到r截止，所以更新区间[(block[r]-1)*blo+1,r] 
        **/
        for(int i = (block[r]-1)*blo+1 ; i <= r ; i++){
            if(vis[block[r]]) break;
            sum[block[r]] -= a[i];
            a[i] = sqrt(a[i]);
            sum[block[r]] += a[i];
        }
    }
    //这里从block[l]+1开始是因为要寻找完整的块 
    for(int i = block[l]+1 ; i <= block[r]-1 ; i++) visSqrt(i);
}

int query(int l,int r){
    int ans = 0;
    for(int i = l ; i <= min(r,block[l]*blo) ; i++) ans += a[i];
    if(block[l] != block[r]){
        for(int i = (block[r]-1)*blo+1 ; i <= r ; i++) ans += a[i];
    }
    for(int i = block[l] + 1 ; i <= block[r]-1 ; i++) ans += sum[i];
    return ans;
}


int main(){
    cin >> n;
    blo = sqrt(n);
    for(int i = 1 ; i <= n ; i++){
        cin >> a[i];
        block[i] = (i-1)/blo + 1; //记录每个数据所处的块号 
        sum[block[i]] += a[i];    //记录每块的和 
    }
    int opt,l,r,c;
    for(int i = 1 ; i <= n ; i++){
        cin >> opt >> l >> r >> c;
        if(opt == 0) update(l,r);
        else cout << query(l,r) << endl;
    }
    return 0;
}