线段树全WA求调,玄关
  • 板块P2068 统计和
  • 楼主PaluAix
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/10/24 19:04
  • 上次更新2023/10/24 19:09:41
查看原帖
线段树全WA求调,玄关
746944
PaluAix楼主2023/10/24 19:04

RT,码风较好

#include <bits/stdc++.h>
#define int long long
#define LC p << 1
#define RC p << 1 | 1
using namespace std;
const int N = 1e6 + 5;

struct P2068 {
  int l, r, val;
} t[N << 3];

void PushUp(int p) {
  t[p].val = t[LC].val + t[RC].val;
}

void Build(int p, int l, int r) {
  t[p].l = l, t[p].r = r;
  if (l == r) {
    t[p].val = 0;
    return;
  }
  int mid = (l + r) >> 1;
  Build(LC, l, mid);
  Build(RC, mid + 1, r);
  PushUp(p);
  return;
}

void PointChange(int p, int x, int v) {
  if (t[p].l == t[p].r) {
    t[p].val += v;
    return;
  }
  int mid = (t[p].l + t[p].r) >> 1;
  if (x <= mid)
    PointChange(LC, x, v);
  else
    PointChange(RC, x, v);
  PushUp(p);
  return;
}

int RangeAsk(int p, int l, int r) {
  if (t[p].l <= l && t[p].r >= r) return t[p].val;
  int mid = (t[p].l + t[p].r) >> 1;
  int ans = 0;
  if (l <= mid) ans += RangeAsk(LC, l, r);
  if (r > mid) ans += RangeAsk(RC, l, r);
  return ans;
}

signed main() {
  int n, q;
  cin >> n >> q;
  Build(1, 1, n);
  for (int i = 1; i <= q; i++) {
    char op;
    int a, b;
    cin >> op >> a >> b;
    if (op == 'x')
      PointChange(1, a, b);
    else
      cout << RangeAsk(1, a, b) << endl;
  }
  system("pause");
  return 0;
}
2023/10/24 19:04
加载中...