题解 P5309 【[Ynoi2011] 初始化】

· · 题解

本来应该是一道不难的分块……结果还是做的很烂。

知识点：阈值分治 + 分块 。

首先我们先考虑一下正常点的数据结构，发现像线段树和树状数组好像生搬硬套都有点难搞，所以考虑暴力数据结构分块。

接着考虑一下直接暴力维护，我们只要判断一下当前的修改次数有没有超过 \sqrt n 次，即判断当前的 x \geq \sqrt n ，这样我们只用考虑 x \leq \sqrt n 的情况了。

分析到这里，我们已经可以想到 Ynoi 题目里面常使用的阈值分治了，而在套路的阈值分治中，通常都是一半暴力一半预处理，我们在这里该怎么预处理呢？

我们再仔细观察操作，发现这个操作是针对全局而言的，那么我们可不可以从宏观大局上来维护呢？

接着又发现如果我们模拟分块，把原序列分成长为 x 的若干块，那么此时每个块内被加上 z 的数的相对位置在当前块中都是一样的，所以我们考虑维护一下这种模拟出来的“小块”的信息即可在计算中做出全局信息。

我们考虑分块查询时是怎么查询的，中间一串连着的块两边一些边角块，由于无法维护所有的 x \leq \sqrt n 的情况，所以我们统计时肯定是有一层循环枚举了 \sqrt n 以内的所有 x ，即我们现在需要 O(1) 算。
考虑均摊时间复杂度。现在我们用一个前缀和以及后缀和来维护每种 x 的信息，在当前 x \leq \sqrt n 的情况下，暴力把前缀和和后缀和更新一下即： 

for(register int i = y ; i <= x ; i ++) pre[x][i] = pre[x][i] + z;
for(register int i = y ; i >= 1 ; i --) suf[x][i] = suf[x][i] + z;

很显然这样的暴力时间复杂度在限制了 x \leq \sqrt n 的情况下不超过 O(\sqrt n) 。

在计算时，我们只要像分块一样计算出左端点在当前 x 的意义下属于那个块，右端点在当前 x 的意义下属于那个块，然后模拟一下分块的查询过程即可。(如果看到这里还有点懵可以看一下代码) 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int Len = 2e5 + 5 , SIZE = 505 , mod = 1e9 + 7;
inline int read() {
    char ch = getchar();
    int x = 0;
    while (ch < '0' || ch > '9') ch = getchar();
    while ('0' <= ch && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x;
}
inline void write(long long x) {
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
int n,m,pos[Len],L[SIZE],R[SIZE],t;
long long sum[SIZE],pre[SIZE][SIZE],suf[SIZE][SIZE],a[Len];
inline void Upd(int x,int y,int z)
{
    if(x >= t) 
    {
        for(register int i = y ; i <= n ; i += x) 
        {
            a[i] = a[i] + z;
            sum[pos[i]] = sum[pos[i]] + z;
        }
    }
    else
    {
        for(register int i = y ; i <= x ; i ++) pre[x][i] = pre[x][i] + z;
        for(register int i = y ; i >= 1 ; i --) suf[x][i] = suf[x][i] + z;
    }
}
inline long long qbsum(int l,int r)
{
    int Lid = pos[l] , Rid = pos[r] ; long long res = 0;
    if(Lid == Rid) for(register int i = l ; i <= r ; i ++) res = res + a[i];
    else
    {
        for(register int i = l ; i <= R[Lid] ; i ++) res = res + a[i];
        for(register int i = Lid + 1 ; i <= Rid - 1 ; i ++) res = res + sum[i];
        for(register int i = L[Rid] ; i <= r ; i ++) res = res + a[i]; 
    }
    return res;
}
inline long long all_sum(int l,int r)
{
    long long Blocksum = qbsum(l , r);
    for(register int i = 1 ; i < t ; i ++)
    {
        int Lb = (l - 1) / i + 1 , Rb = (r - 1) / i + 1;
        if(Lb == Rb) 
        {
            Blocksum -= pre[i][(l - 1) % i];
            Blocksum += pre[i][(r - 1) % i + 1];
        }
        else Blocksum = Blocksum + (Rb - Lb - 1) * pre[i][i] + suf[i][(l - 1) % i + 1] + pre[i][(r - 1) % i + 1];
    }
    return Blocksum % mod;
}
signed main()
{
    n = read() , m = read();
    t = sqrt(n);
    for(register int i = 1 ; i <= n ; i ++) a[i] = read();
    for(register int i = 1 ; i <= t ; i ++) L[i] = (i - 1) * t + 1 , R[i] = i * t;
    R[t] = n;
    for(register int i = 1 ; i <= t ; i ++)
        for(register int j = L[i] ; j <= R[i] ; j ++) pos[j] = i; 
    for(register int i = 1 ; i <= n ; i ++) sum[pos[i]] = sum[pos[i]] + a[i];
    for(register int i = 1 ; i <= m ; i ++)
    {
        int opt,x,y,z;opt = read();
        if(opt == 1){x = read() , y = read() , z = read() , Upd(x , y , z);}
        else{x = read() , y = read() ; write(all_sum(x , y)) , putchar('\n');}
    }
    return 0;
}