分块（区间加，区间乘，单点查询

 1 #include<bits/stdc++.h>
 2 
 3 using namespace std;
 4 typedef long long ll;
 5 const int maxn = 1e5 + 10;
 6 const int inf = 0x3f3f3f3f;
 7 int dir[10][10] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
 8 const int mod = 10007;
 9 int add[maxn], mul[maxn], v[maxn];//记录区间存的加法 区间存的乘法 原数组
10 int opt, a, b, c, t, pos[maxn], l[maxn], r[maxn];
11 
12 inline int read()
13 {
14     char ch = getchar(); int k = 0, f = 1;
15     while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
16     while(ch >= '0' && ch <= '9') {k = (k << 1) + (k << 3) + ch - '0'; ch = getchar();}
17     return k * f;
18 }
19 
20 inline void reset(int x) //更新原数组
21 {
22     for(int i = l[x]; i <= r[x]; ++i)
23     {
24         v[i] = (v[i] * mul[x] + add[x]) % mod;
25     }
26     add[x] = 0, mul[x] = 1; // 记得还原
27 }
28 
29 inline void inser(int a,int b,int c,int k)
30 {
31     int pa = pos[a], pb = pos[b];
32     if(pa == pb)
33     {
34         reset(pa);
35             for(int i = a; i <= b; ++i)
36             {
37                 if(k == 0) v[i] += c;
38                 else v[i] *= c;
39                 v[i] %= mod;
40             }
41     }
42     else
43     {
44         reset(pa);
45         for(int i = a; i <= r[pa]; ++i)
46         {
47             if(k == 0) v[i] += c;
48             else v[i] *= c;
49             v[i] %= mod;
50         }
51         reset(pb);
52         for(int i = l[pb]; i <= b; ++i)
53         {
54             if(k == 0) v[i] += c;
55             else v[i] *= c;
56             v[i] %= mod;
57         }
58         for(int i = pa + 1;i <= pb - 1; ++i)
59         {
60             if(k == 0) add[i] += c;
61             else add[i] *= c, mul[i] *= c; //进行乘法区间更新时如果add数组(加法)存在值,必然需要使其乘上需要乘的数才能保证正确性。
62             add[i] %= mod; mul[i] %= mod;
63         }
64     }
65 }
66 
67 int main()
68 {
69     int n;
70     n = read();
71     for(int i = 1; i <= n; ++i)
72     {
73         v[i]=read();
74     }
75     t = sqrt(n);
76     for(int i = 1; i <= t; ++i)
77     {
78         l[i] = (i - 1) * t + 1;
79         r[i] = i * t;
80     }
81     if(r[t] != n) t++, l[t] = r[t - 1] + 1, r[t] = n;
82     for(int i = 1; i <= t; ++i) mul[i] = 1;
83     for(int i = 1; i <= t; ++i)
84     {
85         for(int j = l[i]; j <= r[i]; ++j)
86         {
87             pos[j] = i;
88         }
89     }
90     for(int i = 1; i <= n; ++i)
91     {
92         opt = read(); a = read(); b = read(); c = read();
93         if(opt != 2) inser(a, b, c, opt);
94         if(opt == 2) cout<<(v[b] * mul[pos[b]] + add[pos[b]]) % mod<<endl;
95     }
96     return 0;
97 }
分块 （区间加，区间乘，单点查询

分块（区间加，区间乘，单点查询
