警示后人：如果你分块70pts

P3372 【模板】线段树 1

湖南省队御用绫厨TM_Sharweek @ 2024-11-29 14:01:50

检查你的分块数组的大小是不是 \sqrt{n}，如果是，改成 \sqrt{n}+50（加上一个你习惯的数字）。因为根号的原因，即使你 n 本来就开大了 50，\sqrt{n} 也基本不会变大（再加上取整，就基本没变了），所以必须单独开大 50。

by JOKER_chu @ 2024-11-29 14:21:12

@湖南省队御用绫厨TM_Sharweek 根号不是直接过了吗，啥都不用改啊

by 湖南省队御用绫厨TM_Sharweek @ 2024-11-29 14:38:55

@JOKER_chu 我的没过/qd

没过

过了

by JOKER_chu @ 2024-11-29 14:46:30

@湖南省队御用绫厨TM_Sharweek 第一次看到常数比我大的（

by 湖南省队御用绫厨TM_Sharweek @ 2024-11-29 14:47:42

@JOKER_chu 别骂了/ll

by JOKER_chu @ 2024-11-29 14:53:52

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 1e5 + 5, B = 317;

ll n, m, b[B], a[N], fix[N], bid[N];

void update(int l, int r, int c){
  if(bid[l] == bid[r]){
    for(int i = l; i <= r; ++i)
      a[i] += c, b[bid[i]] += c;
    return ;
  }
  int i = l, j = r;
  while(bid[i] == bid[l])
    a[i] += c, b[bid[i]] += c, ++i;
  while(bid[j] == bid[r])
    a[j] += c, b[bid[j]] += c, --j;
  for(int k = bid[i]; k <= bid[j]; ++k)
    b[k] += c * B, fix[k] += c;
}

ll query(int l, int r){
  ll ret = 0;
  if(bid[l] == bid[r]){
    for(int i = l; i <= r; ++i) ret += a[i] + fix[bid[i]];
  }else{
    int i = l, j = r;
    while(bid[i] == bid[l])
      ret += a[i] + fix[bid[i]], ++i;
    while(bid[r] == bid[j])
      ret += a[j] + fix[bid[j]], --j;
    for(int k = bid[i]; k <= bid[j]; ++k)
      ret += b[k];
  }
  return ret;
}

int main(){
  ios :: sync_with_stdio(0), cin.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    bid[i] = i / B;
  }
  for(int i = 1, x; i <= n; ++i){
    cin >> a[i];
    b[bid[i]] += a[i];
  }
  for(int i = 1, op, l, r, c; i <= m; ++i){
    cin >> op >> l >> r;
    if(op == 1){
      cin >> c;
      update(l, r, c);
    }else{
      cout << query(l, r) << '\n';
    }
  }
  return 0;
}
@[湖南省队御用绫厨TM_Sharweek](luogu://user/599540)

by JOKER_chu @ 2024-11-29 14:56:19

这还有个我写的常数极大型的

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 1e5 + 5, B = 317;

ll n, m, b[B], a[N], fix[N];

void update(int l, int r, int c){
  if(l / B == r / B){
    for(int i = l; i <= r; ++i)
      a[i] += c, b[i / B] += c;
    return ;
  }
  int i = l, j = r;
  while(i / B == l / B)
    a[i] += c, b[i / B] += c, ++i;
  while(j / B == r / B)
    a[j] += c, b[j / B] += c, --j;
  for(int k = i / B; k <= j / B; ++k)
    b[k] += c * B, fix[k] += c;
}

ll query(int l, int r){
  ll ret = 0;
  if(l / B == r / B){
    for(int i = l; i <= r; ++i) ret += a[i] + fix[i / B];
  }else{
    int i = l, j = r;
    while(i / B == l / B)
      ret += a[i] + fix[i / B], ++i;
    while(r / B == j / B)
      ret += a[j] + fix[j / B], --j;
    for(int k = i / B; k <= j / B; ++k)
      ret += b[k];
  }
  return ret;
}

int main(){
  cin >> n >> m;
  for(int i = 1, x; i <= n; ++i){
    cin >> a[i];
    b[i / B] += a[i];
  }
  for(int i = 1, op, l, r, c; i <= m; ++i){
    cin >> op >> l >> r;
    if(op == 1){
      cin >> c;
      update(l, r, c);
    }else{
      cout << query(l, r) << '\n';
    }
  }
  return 0;
}

这个也过了，最慢的点 120ms+

块长向下取整后 316 \times 316 < 10^5，但是我不知道为啥会 T（

|