分块入门求条

->7

#include <bits/stdc++.h>
#define int long long
#define mod(x) (x % 10007)
using namespace std;
int n;
const int N = 5e5 + 5;
int pos[N], lz1[N], lz2[N], st[N], ed[N], a[N];

void init()
{
    int block = sqrt(n), cnt = n / block;
    if(n % block) cnt ++ ;
    for(int i = 1;i <= cnt;i ++ ) st[i] = (i - 1) * block + 1, ed[i] = i * block;
    ed[cnt] = n;
    for(int i = 1;i <= cnt;i ++ ){
        for(int j = st[i];j <= ed[i];j ++ ) pos[j] = i;
    }
    for(int i = 1;i <= pos[n];i ++ ) lz2[i] = 1, lz1[i] = 0;
}

void push(int x)
{
    for(int i = st[x];i <= ed[x];i ++ ) a[i] = mod(a[i] * lz2[x] + lz1[x]);
    lz1[x] = 0, lz2[x] = 1;
}

void update1(int x, int y, int val)
{
    int p = pos[x], q = pos[y];
    if(p == q)
    {
        push(p);
        for(int i = x;i <= y;i ++ ) a[i] = mod(a[i] + val);
    }
    else {
        for(int i = p + 1;i < q;i ++ ) lz1[i] = mod(lz1[i] + val);
        push(p);
        for(int i = x;i <= ed[p];i ++ ) a[i] = mod(a[i] + val);
        push(q);
        for(int i = st[q];i <= y;i ++ ) a[i] = mod(a[i] + val);
    }
}

void update2(int x, int y, int val)
{
    int p = pos[x], q = pos[y];
    if(p == q)
    {
        push(p);
        for(int i = x;i <= y;i ++ ) a[i] = mod(a[i] * val);
    }
    else {
        for(int i = p + 1;i < q;i ++ ) lz1[i] = mod(lz1[i] * val), lz2[i] = mod(lz2[i] * val);
        push(p);
        for(int i = x;i <= ed[p];i ++ ) a[i] = mod(a[i] * val);
        push(q);
        for(int i = st[q];i <= y;i ++ ) a[i] = mod(a[i] * val);
    }
}

signed main()
{
    cin >> n;
    for(int i = 1;i <= n;i ++ ) cin >> a[i];
    init();
    int r = 1;
    for(int i = 1;i <= n;i ++ ){
        int opt, l, r, c;
        cin >> opt >> l >> r >> c;
        if(opt == 0) update1(l, r, c);
        else if(opt == 1) update2(l, r, c);
        else cout << (a[r] * lz2[pos[r]] + lz1[pos[r]]) % 10007 << endl;
    }
    return 0;
}