fork(9) download
  1. #include <cstdio>
  2. #include <algorithm>
  3. using namespace std;
  4.  
  5. int n, m, t, l, r, x, mark[410000];
  6. long long delta[410000], sum[410000];
  7.  
  8. void read(int &x) {
  9. char k;
  10. for (k = getchar(); k <= 32; k = getchar());
  11. for (x = 0; '0' <= k; k = getchar()) x = x * 10 + k - '0';
  12. }
  13.  
  14. void mkt(int k, int q, int h) {
  15. if (q < h) {
  16. mkt(k * 2, q, (q + h) / 2);
  17. mkt(k * 2 + 1, (q + h) / 2 + 1, h);
  18. mark[k] = 0;
  19. }else mark[k] = q;
  20. }
  21.  
  22. long long query(int k, int q, int h, int l, int r) {
  23. if (l <= q && h <= r) return sum[k];
  24. if (r <= (q + h) / 2) return query(k * 2, q, (q + h) / 2, l, r) + 1LL * delta[k] * (r - l + 1);
  25. if ((q + h) / 2 < l) return query(k * 2 + 1, (q + h) / 2 + 1, h, l, r) + 1LL * delta[k] * (r - l + 1);
  26. return query(k * 2, q, (q + h) / 2, l, (q + h) / 2) + query(k * 2 + 1, (q + h) / 2 + 1, h, (q + h) / 2 + 1, r) + 1LL * delta[k] * (r - l + 1);
  27. }
  28.  
  29. void Clear(int k, int q, int h) {
  30. if (mark[k] > 0) {
  31. delta[k] += abs(mark[k] - x);
  32. sum[k] += 1LL * abs(mark[k] - x) * (h - q + 1);
  33. }else {
  34. Clear(k * 2, q, (q + h) / 2);
  35. Clear(k * 2 + 1, (q + h) / 2 + 1, h);
  36. sum[k] = sum[k * 2] + sum[k * 2 + 1] + 1LL * delta[k] * (h - q + 1);
  37. }
  38. mark[k] = -1;
  39. }
  40.  
  41. void modify(int k, int q, int h) {
  42. if (l <= q && h <= r) Clear(k, q, h), mark[k] = x;
  43. else {
  44. if (mark[k] > 0) mark[k * 2] = mark[k * 2 + 1] = mark[k], mark[k] = 0;
  45. if (r <= (q + h) / 2) modify(k * 2, q, (q + h) / 2);
  46. else if ((q + h) / 2 < l) modify(k * 2 + 1, (q + h) / 2 + 1, h);
  47. else modify(k * 2, q, (q + h) / 2), modify(k * 2 + 1, (q + h) / 2 + 1, h);
  48. mark[k] = 0;
  49. sum[k] = sum[k * 2] + sum[k * 2 + 1] + 1LL * delta[k] * (h - q + 1);
  50. }
  51. }
  52.  
  53. int main() {
  54. read(n); read(m);
  55. mkt(1, 1, n);
  56. while (m--) {
  57. read(t); read(l); read(r);
  58. if (t == 1) {
  59. read(x);
  60. modify(1, 1, n);
  61. }else {
  62. printf("%I64d\n", query(1, 1, n, l, r));
  63. }
  64. }
  65. }
  66.  
Time limit exceeded #stdin #stdout 5s 11304KB
stdin
Standard input is empty
stdout
Standard output is empty