难点：

  • 乘法懒标记和加法懒标记的处理顺序，pushDown函数
  • 区间乘法对加法标记的影响，mulSegment函数
  • 建树的优化，built函数
  • 查询函数的优化，query函数
  • 数据庞大，如何贯彻执行取模
  • 精度问题：干脆都用long long吧.jpg

代码

  1. #include<iostream>
  2. #include<cstdio>
  3. using namespace std;
  4. typedef long long ll;
  5. const int maxn = 1e5 + 7;
  6. ll a[maxn];
  7. int n, m, mod;
  8. struct node {
  9.     ll l, r;
  10.     ll sum, mul, add;
  11. }st[4*maxn];
  12. /*构建树*/
  13. void built(int i, ll l, ll r) {
  14.     st[i].l = l; st[i].r = r;  
  15.     st[i].add = 0; st[i].mul = 1;
  16.     if (l == r) {  
  17.         st[i].sum = a[l] % mod;
  18.         return;
  19.     }
  20.     ll mid = (l + r) / 2;
  21.     built(2 * i, l, mid);
  22.     built(2 * i + 1, mid + 1, r);
  23.     st[i].sum = (st[2 * i].sum + st[2 * i + 1].sum) % mod;  //回溯
  24. }
  25. /*下推标记（核心代码）*/
  26. void pushDown(int i) {
  27.     //如果是叶节点
  28.     if (st[i].l == st[i].r) return;
  30.     ll mid = (st[i].l + st[i].r) / 2;
  31.     //维护左右子节点区间值
  32.     st[2 * i].sum = (ll)(st[2 * i].sum * st[i].mul + ((st[2 * i].r - st[2 * i].l + 1) * st[i].add) % mod) % mod;
  33.     st[2 * i + 1].sum = (ll)(st[2 * i + 1].sum * st[i].mul + ((st[2 * i + 1].r - st[2 * i + 1].l + 1) * st[i].add) % mod) % mod;
  34.     //维护左右子节点懒标记
  35.     st[2 * i].mul = (ll)(st[2 * i].mul * st[i].mul) % mod;
  36.     st[2 * i + 1].mul = (ll)(st[2 * i + 1].mul * st[i].mul) % mod;
  38.     st[2 * i].add = (ll)(st[2 * i].add * st[i].mul + st[i].add) % mod;
  39.     st[2 * i + 1].add = (ll)(st[2 * i + 1].add * st[i].mul + st[i].add) % mod;
  40.     //父节点初始化
  41.     st[i].mul = 1;
  42.     st[i].add = 0;
  43. }
  44. /*区间加*/
  45. void addSegment(int i, ll x, ll y, ll k) {
  46.     if (x <= st[i].l && st[i].r <= y) {
  47.         st[i].sum = (ll)(st[i].sum + (st[i].r - st[i].l + 1) * k) % mod;
  48.         st[i].add = (st[i].add + k) % mod;
  49.         return;
  50.     }
  51.     pushDown(i);
  52.     ll mid = (st[i].l + st[i].r) / 2;
  53.     if (x <= mid) addSegment(2 * i, x, y, k);
  54.     if (y > mid) addSegment(2 * i + 1, x, y, k);
  55.     st[i].sum = (st[2 * i].sum + st[2 * i + 1].sum) % mod;  //回溯
  56. }
  57. /*区间乘*/
  58. void mulSegment(int i, ll x, ll y, ll k) {
  59.     if (x <= st[i].l && st[i].r <= y) {
  60.         st[i].sum = (st[i].sum * k) % mod;
  61.         st[i].add = (st[i].add * k) % mod;  //(重要步骤)
  62.         st[i].mul = (st[i].mul * k) % mod;
  63.         return;
  64.     }
  65.     pushDown(i);
  66.     ll mid = (st[i].l + st[i].r) / 2;
  67.     if (x <= mid) mulSegment(2 * i, x, y, k);
  68.     if (y > mid) mulSegment(2 * i + 1, x, y, k);
  69.     st[i].sum = (st[2 * i].sum + st[2 * i + 1].sum) % mod;  //回溯
  70. }
  71. /*查询*/
  72. ll query(int i, ll x, ll y) {
  73.     if (x <= st[i].l && st[i].r <= y) return st[i].sum % mod;
  74.     pushDown(i);  //重要点
  75.     ll ans = 0;
  76.     ll mid = (st[i].l + st[i].r) / 2;
  77.     if (x <= mid) ans = (ans + query(2 * i, x, y)) % mod;
  78.     if (y > mid) ans = (ans + query(2 * i + 1, x, y)) % mod;
  79.     return ans;
  80. }
  81. int main() {
  82.     cin >> n >> m >> mod;
  83.     for (int i = 1; i <= n; i++) {
  84.         //scanf_s("%lld", &a[i]);  
  85.         scanf("%lld", &a[i]);  
  86.     }
  87.     built(1, 1, n);
  88.     int flag;
  89.     ll x, y, k;
  90.     for (int i = 1; i <= m; i++) {
  91.         //scanf_s("%d", &flag);  
  92.         scanf("%d", &flag);
  93.         if (flag == 1) {
  94.             //scanf_s("%lld%lld%lld", &x, &y, &k);  
  95.             scanf("%lld%lld%lld", &x, &y, &k);
  96.             mulSegment(1, x, y, k);
  97.         }
  98.         else if (flag == 2) {
  99.             //scanf_s("%lld%lld%lld", &x, &y, &k); 
  100.             scanf("%lld%lld%lld", &x, &y, &k);
  101.             addSegment(1, x, y, k);
  102.         }
  103.         else {
  104.             //scanf_s("%lld%lld", &x, &y);
  105.             scanf("%lld%lld", &x, &y);
  106.             //printf_s("%lld\n", query(1, x, y));
  107.             printf("%lld\n", query(1, x, y));
  108.         }
  109.     }
  110.     return 0;
  111. }

BUG

第一次

  1. /*下推标记（错误代码）*/
  2. void pushDown(int i) {
  3.     //如果是叶节点
  4.     if (st[i].l == st[i].r) return;
  6.     ll mid = (st[i].l + st[i].r) / 2;
  7.     //维护左右子节点区间值
  8.     st[2 * i].sum = (ll)(st[2 * i].sum * st[i].mul + ((st[2 * i].r - st[2 * i].l + 1) * st[i].add)%mod) % mod;
  9.     st[2 * i + 1].sum = (ll)(st[2 * i + 1].sum * st[i].mul + ((st[2 * i + 1].r - st[2 * i + 1].l + 1) * st[i].add)%mod) % mod;
  10.     //维护左右子节点懒标记
  11.     st[2 * i].mul = (ll)(st[2 * i].mul * st[i].mul) % mod;
  12.     st[2 * i + 1].mul = (ll)(st[2 * i + 1].mul * st[i].mul) % mod;
  14.     st[2 * i].add = (ll)(st[2 * i].add * st[i].mul + st[2 * i].add) % mod;
  15.     st[2 * i + 1].add = (ll)(st[2 * i + 1].add * st[i].mul + st[2 * i + 1].add) % mod;
  16.     //父节点初始化
  17.     st[i].mul = 1;
  18.     st[i].add = 0;
  19. }
  20. /*下推标记（正确代码）*/
  21. void pushDown(int i) {
  22.     //如果是叶节点
  23.     if (st[i].l == st[i].r) return;
  25.     ll mid = (st[i].l + st[i].r) / 2;
  26.     //维护左右子节点区间值
  27.     st[2 * i].sum = (ll)(st[2 * i].sum * st[i].mul + ((st[2 * i].r - st[2 * i].l + 1) * st[i].add)%mod) % mod;
  28.     st[2 * i + 1].sum = (ll)(st[2 * i + 1].sum * st[i].mul + ((st[2 * i + 1].r - st[2 * i + 1].l + 1) * st[i].add)%mod) % mod;
  29.     //维护左右子节点懒标记
  30.     st[2 * i].mul = (ll)(st[2 * i].mul * st[i].mul) % mod;
  31.     st[2 * i + 1].mul = (ll)(st[2 * i + 1].mul * st[i].mul) % mod;
  33.     st[2 * i].add = (ll)(st[2 * i].add * st[i].mul + st[i].add) % mod;  //
  34.     st[2 * i + 1].add = (ll)(st[2 * i + 1].add * st[i].mul + st[i].add) % mod;  //
  35.     //父节点初始化
  36.     st[i].mul = 1;
  37.     st[i].add = 0;
  38. }
  39. /*区间乘（错误代码）*/
  40. void mulSegment(int i, ll x, ll y, ll k) {
  41.     if (x <= st[i].l && st[i].r <= y) {
  42.         st[i].sum = (st[i].sum * k) % mod;
  43.         st[i].add = (st[i].add * k) % mod;  //(重要步骤)
  44.         st[i].mul = (st[i].mul * k) % mod;
  45.     }
  46.     pushDown(i);
  47.     ll mid = (st[i].l + st[i].r) / 2;
  48.     if (x <= mid) mulSegment(2 * i, x, y, k);
  49.     if (y > mid) mulSegment(2 * i + 1, x, y, k);
  50.     st[i].sum = (st[2 * i].sum + st[2 * i + 1].sum) % mod;  //回溯
  51. }
  52. /*区间乘（正确代码）*/
  53. void mulSegment(int i, ll x, ll y, ll k) {
  54.     if (x <= st[i].l && st[i].r <= y) {
  55.         st[i].sum = (st[i].sum * k) % mod;
  56.         st[i].add = (st[i].add * k) % mod;  //(重要步骤)
  57.         st[i].mul = (st[i].mul * k) % mod;
  58.         return;  //
  59.     }
  60.     pushDown(i);
  61.     ll mid = (st[i].l + st[i].r) / 2;
  62.     if (x <= mid) mulSegment(2 * i, x, y, k);
  63.     if (y > mid) mulSegment(2 * i + 1, x, y, k);
  64.     st[i].sum = (st[2 * i].sum + st[2 * i + 1].sum) % mod;  //回溯
  65. }
  66. /*查询（错误代码，两个错误）*/
  67. ll query(int i, ll x, ll y) {
  68.     if (x <= st[i].l && st[i].r <= y) return st[i].sum % mod;
  69.     ll ans = 0;
  70.     ll mid = (st[i].l + st[i].r) / 2;
  71.     if (x <= mid) ans = (ans + st[2 * i].sum) % mod;
  72.     if (y > mid) ans = (ans + st[2 * i + 1].sum) % mod;
  73.     return ans;
  74. }
  75. /*查询（正确代码）*/
  76. ll query(int i, ll x, ll y) {
  77.     if (x <= st[i].l && st[i].r <= y) return st[i].sum % mod;
  78.     pushDown(i);  //重要点
  79.     ll ans = 0;
  80.     ll mid = (st[i].l + st[i].r) / 2;
  81.     if (x <= mid) ans = (ans + query(2 * i, x, y)) % mod;  //
  82.     if (y > mid) ans = (ans + query(2 * i + 1, x, y)) % mod;  //
  83.     return ans;
  84. }

第二次

  1. /*区间乘（错误代码）*/
  2. void mul(ll i, ll x, ll y, ll k) {
  3.     if (x <= st[i].l && st[i].r <= y) {
  4.         st[i].sum = (st[i].sum * k) % mod;
  5.         st[i].mul = (st[i].mul * k) % mod;
  6.         st[i].add = (st[i].add * k) % mod;  //对于加动作之后的乘动作，add记录下来
  7.         return;
  8.     }
  9.     pushDown(i);  //WRONG POINT
  10.     ll mid = (st[i].l + st[i].r) / 2;
  11.     if (x <= st[i].l) mul(2 * i, x, y, k);
  12.     if (y > st[i].r) mul(2 * i + 1, x, y, k);
  13.     st[i].sum = (st[2 * i].sum + st[2 * i + 1].sum) % mod;
  14. }
  15. /*区间乘（正确代码）*/
  16. void mul(ll i, ll x, ll y, ll k) {
  17.     if (x <= st[i].l && st[i].r <= y) {
  18.         st[i].sum = (st[i].sum * k) % mod;
  19.         st[i].mul = (st[i].mul * k) % mod;
  20.         st[i].add = (st[i].add * k) % mod;  //对于加动作之后的乘动作，add记录下来
  21.         return;
  22.     }
  23.     pushDown(i);  //WRONG POINT
  24.     ll mid = (st[i].l + st[i].r) / 2;
  25.     if (x <= mid) mul(2 * i, x, y, k);  //
  26.     if (y > mid) mul(2 * i + 1, x, y, k);  //
  27.     st[i].sum = (st[2 * i].sum + st[2 * i + 1].sum) % mod;
  28. }
  29. /*查询（错误代码）*/
  30. ll query(int i, ll x, ll y) {
  31.     if (x <= st[i].l && st[i].r <= y) return st[i].sum % mod;
  32.     ll ans = 0;
  33.     ll mid = (st[i].l + st[i].r) / 2;
  34.     if (x <= mid) ans = (ans + query(2 * i, x, y)) % mod;
  35.     if (y > mid) ans = (ans + query(2 * i + 1, x, y)) % mod;
  36.     return ans;
  37. }
  38. /*查询（正确代码）*/
  39. ll query(int i, ll x, ll y) {
  40.     if (x <= st[i].l && st[i].r <= y) return st[i].sum % mod;
  41.     pushDown(i);  //
  42.     ll ans = 0;
  43.     ll mid = (st[i].l + st[i].r) / 2;
  44.     if (x <= mid) ans = (ans + query(2 * i, x, y)) % mod;
  45.     if (y > mid) ans = (ans + query(2 * i + 1, x, y)) % mod;
  46.     return ans;
  47. }
  48. /*建树没有贯彻取模*/
  49. void built(ll i, ll l, ll r) {
  50.     st[i].l = l; st[i].r = r;
  51.     st[i].add = 0; st[i].mul = 1;
  52.     if (l == r) {
  53.         st[i].sum = a[l] % mod;
  54.         return;
  55.     }
  56.     ll mid = (l + r) / 2;
  57.     built(2 * i, l, mid);
  58.     built(2 * i + 1, mid + 1, r);
  59.     st[i].sum = (st[2 * i].sum + st[2 * i + 1].sum) % mod;  //错误：没有贯彻取模
  60. }

第三次 一遍AC

  1. #include<iostream>
  2. #include<cstdio>
  3. using namespace std;
  4. typedef long long ll;
  5. const int maxn = 1e5 + 10;
  6. ll n, m, mod;
  7. ll a[maxn];
  8. struct NODE {
  9.     ll l, r, sum;
  10.     ll add, mu;
  11. }t[4*maxn];
  12. /*built*/
  13. void built(ll i, ll l, ll r) {
  14.     t[i].l = l; t[i].r = r;
  15.     t[i].mu = 1; t[i].add = 0;
  16.     if (l == r) {
  17.         t[i].sum = a[l] % mod;
  18.         return;
  19.     }
  20.     ll mid = (l + r) / 2;
  21.     built(2 * i, l, mid);
  22.     built(2 * i + 1, mid + 1, r);
  23.     t[i].sum = (t[2 * i].sum + t[2 * i + 1].sum) % mod;
  24. }
  25. /*pushDown*/
  26. void pushDown(ll i) {
  27.     if (t[i].l == t[i].r) return;
  29.     t[2 * i].sum = (t[2 * i].sum * t[i].mu + (t[2 * i].r - t[2 * i].l + 1) * t[i].add) % mod;
  30.     t[2 * i + 1].sum = (t[2 * i + 1].sum * t[i].mu + (t[2 * i + 1].r - t[2 * i + 1].l + 1) * t[i].add) % mod;
  32.     t[2 * i].mu = (t[2 * i].mu * t[i].mu) % mod;
  33.     t[2 * i + 1].mu = (t[2 * i + 1].mu * t[i].mu) % mod;
  34.     t[2 * i].add = (t[2 * i].add * t[i].mu + t[i].add) % mod;
  35.     t[2 * i + 1].add = (t[2 * i + 1].add * t[i].mu + t[i].add) % mod;
  37.     t[i].mu = 1;
  38.     t[i].add = 0;
  39. }
  40. /*add*/
  41. void add(ll i, ll x, ll y, ll k) {
  42.     if (x <= t[i].l && t[i].r <= y) {
  43.         t[i].sum = (t[i].sum + (t[i].r - t[i].l + 1) * k) % mod;
  44.         t[i].add = (t[i].add + k) % mod;
  45.         return;
  46.     }
  47.     pushDown(i);  //POINT
  48.     ll mid = (t[i].l + t[i].r) / 2;
  49.     if (x <= mid) add(2 * i, x, y, k);
  50.     if (y > mid) add(2 * i + 1, x, y, k);
  51.     t[i].sum = (t[2 * i].sum + t[2 * i + 1].sum) % mod;
  52. }
  53. /*multiply*/
  54. void mul(ll i, ll x, ll y, ll k) {
  55.     if (x <= t[i].l && t[i].r <= y) {
  56.         t[i].sum = (t[i].sum * k) % mod;
  57.         t[i].mu = (t[i].mu * k) % mod;
  58.         t[i].add = (t[i].add * k) % mod;  //POINT
  59.         return;
  60.     }
  61.     pushDown(i);  //POINT
  62.     ll mid = (t[i].l + t[i].r) / 2;
  63.     if (x <= mid) mul(2 * i, x, y, k);
  64.     if (y > mid) mul(2 * i + 1, x, y, k);
  65.     t[i].sum = (t[2 * i].sum + t[2 * i + 1].sum) % mod;
  66. }
  67. /*find*/
  68. ll query(ll i, ll x, ll y) {
  69.     if (x <= t[i].l && t[i].r <= y) {
  70.         return t[i].sum % mod;
  71.     }
  72.     pushDown(i);  //POINT
  73.     ll mid = (t[i].l + t[i].r) / 2;
  74.     ll ans = 0;
  75.     if (x <= mid) ans = (ans + query(2 * i, x, y)) % mod;
  76.     if (y > mid) ans = (ans + query(2 * i + 1, x, y)) % mod;
  77.     return ans;
  78. }
  79. int main() {
  80.     scanf("%lld%lld%lld", &n, &m, &mod);
  81.     for (int i = 1; i <= n; i++) {
  82.         scanf("%lld", &a[i]);
  83.     }
  84.     built(1, 1, n);
  85.     int flag;
  86.     ll x, y, k;
  87.     for (int i = 1; i <= m; i++) {
  88.         scanf("%d", &flag);
  89.         if (flag == 1) {
  90.             scanf("%lld%lld%lld", &x, &y, &k);
  91.             mul(1, x, y, k);
  92.         }
  93.         else if (flag == 2) {
  94.             scanf("%lld%lld%lld", &x, &y, &k);
  95.             add(1, x, y, k);
  96.         }
  97.         else {
  98.             scanf("%lld%lld", &x, &y);
  99.             printf("%lld\n", query(1, x, y));
  100.         }
  101.     }
  102.     return 0;
  103. }