题解 CF86D 【Powerful array】

· · 题解

本题标签：分块！！！

哎发现大佬们人均会莫队，但是蒟蒻不会莫队，于是我只好用分块来献丑了qaq~

希望能够给大家多一个思路&让一些人了解一下分块（虽然我觉得会莫队的应该没有不会分块的）

鉴于这是一个比较基础的分块题，在此之前先介绍一下分块

其实分块的思想非常简单

大体思想：

分块就是把一段数分成几块来做

分块的操作一般是维护和查询，一个对于[l，r]的操作，对于在该区间内的完整的块，我们直接维护整个块的信息；对于两侧不完整的部分，我们暴力修改每个点的信息。写分块的关键就是想好如何维护和查询。

一般情况下，当S=\sqrt{N}时，时空复杂度最优。

解决问题：

分块可以处理很多区间问题，虽然复杂度要比树状数组和线段树要高，但是代码比较简短、思想直观形象，所以很多题不会求解可以考虑分块一下

具体实现

分块分块，首先自然需要分，在这里给出一个小栗子：这里是通过分块来维护区间最大值

void build()
{
    dis=sqrt(n);                    //每个块的长度
    num=n/dis;                      //共有多少个块
    for (int i=1;i<=num;i++)        //给每一个块标记左右范围
    {
        l[i]=dis*(i-1)+1;
        r[i]=dis*i;
    }
    r[num]=n;                       //最后一个r dis*i有可能大于n故要改回n
    for (int i=1;i<=num;i++)
    {
        int ans=0;
        for (int j=l[i];j<=r[i];j++)
        {
            ans=max(ans,a[j]);      //具体题目具体分析，此题中要求维护区间最大值故记录区间最大值
            block[j]=i;             //记录没一个点属于哪一个块
        }
        maxx[i]=ans;
    }
}
}

相信通过这个大家能对分块的思想有一个基本的了解，接下来我们回到这一题~

题目大意：

给出一个n个数组成的数列a_1...a_n，有t次询问，每次询问为一个[l,r]的区间，求区间内每种数字出现次数的平方×数字的值的和。

思路：

发现这是一个标准的纯查询的问题，我们考虑用分块做

我们可以这样做：

但是我们应该加什么呢？对于一个已经出现了x次的数a_i,x^2\cdot a_i变成了(x+1)^2\cdot a_i

而根据完全平方公式可知

(x+1)^2=x^2+2\cdot x+1

所以只需加上(2\cdot x+1)\cdot a_i即可，于是这就变成了一个比较暴力的问题

ok,如果大家对这个代码是否能过表示怀疑的话我们不妨来算一下复杂度，t次询问

具体代码不再展示，希望对你能够有帮助