题解 P1438 【无聊的数列】

hellowin · 2019-09-20 14:08:59 · 题解

分块好题

为什么神仙都会线段树啊。

不知道怎么写。

题解

先考虑块内如何维护。

我们维护一个首项和公差，因为两个项数相同的等差数列的和还是一个等差数列。

考虑到这个性质，我们只需要维护出第x块的首项和公差就可以维护这个块内所有的数，再次加上等差数列时，只需要首项和公差的叠加。

对于边角料部分，直接暴力加值。

其实这道题维护区间和的话可能分块会卡不过去。

时间复杂度O(m\sqrt n)

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
int block, sum, Ans[500005], p[500005], n, m, Add[500005], Fir[500005], delta[500005];
int a[500005];
inline void work(int as, int bs, int x) {
    int st = 0;
    for (int i = as; i <= bs; i++) st += a[i];
    Add[x] += st;
    // COp[x] = st;
}
inline int read() {
    int s = 0, w = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
    return s * w;
}
signed main() {
    scanf("%lld%lld", &n, &m);
    block = (int)sqrt(n);
    sum = n / block;
    if (n % block)
        sum++;
    for (int i = 1; i <= n; i++) {
        a[i] = read();
        p[i] = (i - 1) / block + 1;
    }
    for (int i = 1; i <= sum; i++) work((i - 1) * block + 1, i * block, i);
    for (int i = 1; i <= m; i++) {
        int x, y, st = 0, op, k, mp, io;
        op = read();
        if (op == 2) {
            x = read();
            //y = read(); 
            y = x;
            for (int j = x; j <= min(p[x] * block, y); j++) st += a[j] + Fir[p[j]] + delta[p[j]] * (j - (p[x] - 1) * block - 1);
            //cout<<st<<endl;
            if (p[x] != p[y])
                for (int j = (p[y] - 1) * block + 1; j <= y; j++) st += a[j] + Fir[p[j]] + delta[p[j]] * (j - (p[y] - 1) * block - 1);
            //cout<<st<<endl;
            for (int j = p[x] + 1; j <= p[y] - 1; j++) st += Add[j];
            printf("%d\n", st);
        } else {
            x = read();
            y = read();
            int fir,del;
            fir = read();
            del = read();
            for (int j = x; j <= min(p[x] * block, y); j++) {
                Add[p[j]] += fir + del * (j - x);
                a[j] += fir + del * (j - x);
                //cout<<fir + del * (j - x)<<" "<<j<<endl;
            }
            if (p[x] != p[y])
                for (int j = (p[y] - 1) * block + 1; j <= y; j++) {
                Add[p[j]] += fir + del * (j - x);
                a[j] += fir + del * (j - x);
                //cout<<fir + del * (j - x)<<" "<<j<<endl;
            }
            for (int j = p[x] + 1; j <= p[y] - 1; j++)
            {
              Add[j] += (fir + del * ((j - 1) * block + 1 - x) + fir + del * (j * block - x)) * block / 2;  
              Fir[j] += fir + del * ((j - 1) * block + 1 - x);
              delta[j] += del;
             // cout<<fir + del * ((j - 1) * block + 1 - x<<" "<<fir + del * (j * block - x)
            }
        }
    }
    return 0;
}