题解：P13982 数列分块入门 7

DrDuck · 2025-09-06 14:36:47 · 题解

传播分块邪恶思想

类似 P3373，维护一个加标记 taga，乘标记 tagb。下传时先下传乘标记再下传加标记，所以要考虑乘标记对加标记的影响。

对于整块：

• 如果是加操作，taga 加上 c。
• 如果是乘操作，taga 和 tagb 都乘上 c。

对于散块，先像线段树一样下传懒标记再暴力修改即可。

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

CODE

#include<bits/stdc++.h>
#define int long long
#define void inline void
using namespace std;
const int maxn = 3e+5 + 5, kMaxN = 550, mod = 10007;
int n, sq;
int a[maxn], tag1[kMaxN], tag2[kMaxN], L[kMaxN], R[kMaxN], bel[maxn], b[maxn], c[maxn];
void build()
{
    sq = sqrt(n);
    int len = n / sq;
    for (int i = 1; i <= sq; i++)
    {
        L[i] = R[i - 1] + 1;
        R[i] = L[i] + len - 1;
    }
    if (R[sq] < n)
    {
        sq++;
        L[sq] = R[sq - 1] + 1;
        R[sq] = n;
    }
    for (int i = 1; i <= sq; i++)
    {
        tag2[i] = 1;
        for (int j = L[i]; j <= R[i]; j++)
        {
            // cout << "j: " << j << " i: " << i << '\n';
            b[j] = 1;
            bel[j] = i;
        }
    }
}
void pushdown(int p)
{
    for (int i = L[p]; i <= R[p]; i++)
    {
        a[i] = (a[i] * tag2[p] % mod + tag1[p]) % mod;
    }
    tag2[p] = 1, tag1[p] = 0;
}
void update_part_1(int l, int r, int val)
{
    pushdown(bel[l]);
    for (int i = l; i <= r; i++)
    {
        a[i] = (a[i] + val) % mod;
    }
}
void update_part_2(int l, int r, int val)
{
    pushdown(bel[l]);
    for (int i = l; i <= r; i++)
    {
        a[i] = a[i] * val % mod;
    }
}
void update_1(int l, int r, int val)
{
    if (bel[r] == bel[l])
    {
        update_part_1(l, r, val);
        return;
    }
    update_part_1(l, R[bel[l]], val);
    update_part_1(L[bel[r]], r, val);
    for (int i = bel[l] + 1; i < bel[r]; i++)
    {
        tag1[i] = (tag1[i] + val) % mod;
    }
}
void update_2(int l, int r, int val)
{
    if (bel[r] == bel[l])
    {
        update_part_2(l, r, val);
        return;
    }
    update_part_2(l, R[bel[l]], val);
    update_part_2(L[bel[r]], r, val);
    for (int i = bel[l] + 1; i < bel[r]; i++)
    {
        tag1[i] = tag1[i] * val % mod;
        tag2[i] = tag2[i] * val % mod;
    }
}
inline int query(int x)
{
    return (a[x] * tag2[bel[x]] % mod + tag1[bel[x]] * b[x] % mod) % mod;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    build();
    for (int i = 1; i <= n; i++)
    {
        int opt, l, r, c;
        cin >> opt >> l >> r >> c;
        if (opt == 0)
        {
            update_1(l, r, c);
        }
        else if (opt == 1)
        {
            update_2(l, r, c);
        }
        else
        {
            cout << (query(r) + mod) % mod << '\n';
        }
    }
    return 0;   
}