2024算法基础公选课练习六（综合3）

一、前言

最后三题有点难度，其他都还是比较基础的，前面题我直接放代码了

二、题目总览

三、具体题目

3.1 问题 A: 一锐家的电池

我的代码

#include <bits/stdc++.h>
using i64 = long long;
using pii = std::pair<int,int>;
constexpr int N = 1e5+5,M = 1e6+5,INF = 0x3f3f3f3f;

void solve(){
int n;std::cin >> n;
std::vector<std::string> v(N);
int ans = 1;
for(int i = 0;i<n;++i){
std::cin >> v[i];
}
for(int i = 1;i<n;++i){
if(v[i]!=v[i-1]){
++ans;
}
}
std::cout << ans << '\n';
}
int main(){
  std::cin.tie(nullptr)->sync_with_stdio(false);

  int t = 1;
  // std::cin >> t;
  for(int ti = 0;ti<t;++ti) {
      solve();
  }

  return 0;
}

3.2 问题 B: 新年礼物

我的代码

#include <bits/stdc++.h>
using i64 = long long;
using pii = std::pair<int,int>;
constexpr int N = 1e5+5,M = 1e6+5,INF = 0x3f3f3f3f;

void solve(){
int n,m;std::cin >> n >> m;
std::vector<int> v(105,0);
for(int i = 1;i<=m;++i) std::cin >> v[i];
std::sort(v.begin()+1,v.begin()+1+m);
int ans = INF;
for(int i = 1;i<=m-n+1;++i){
int min = v[i],max = v[i+n-1];
ans = std::min(ans,max-min);
}
std::cout << ans << '\n';
}
int main(){
  std::cin.tie(nullptr)->sync_with_stdio(false);

  int t = 1;
  // std::cin >> t;
  for(int ti = 0;ti<t;++ti) {
      solve();
  }

  return 0;
}

3.3 问题 C: 虎哥坐公交

我的代码

#include <bits/stdc++.h>
using i64 = long long;
using pii = std::pair<int,int>;
constexpr int N = 1e5+5,M = 1e6+5,INF = 0x3f3f3f3f;

int n,t;
std::vector<pii> v(N);
void solve(){
std::cin >> n >> t;

for(int i = 1;i<=n;++i){
std::cin >> v[i].first >> v[i].second;
}

std::vector<int> ans;
for(int i = 1;i<=n;++i){
if(t<=v[i].first){
ans.emplace_back(v[i].first);
}else{
int tmp = ((t-v[i].first)+v[i].second-1)/v[i].second;
tmp = v[i].first+tmp*v[i].second;
ans.emplace_back(tmp);
}
}

int min = INF,res = -1;
for(int i = 0;i<ans.size();++i){
if(ans[i]<min){
min = ans[i],res = i+1;
}
}
std::cout << res << '\n';
}
int main(){
  std::cin.tie(nullptr)->sync_with_stdio(false);

  int t = 1;
  // std::cin >> t;
  for(int ti = 0;ti<t;++ti) {
      solve();
  }

  return 0;
}

3.4 问题 D: 跳格子

我的代码

#include <bits/stdc++.h>
using i64 = long long;
using pii = std::pair<int,int>;
constexpr int N = 1e5+5,M = 1e6+5,INF = 0x3f3f3f3f;


int __lcm(int a,int b){
return a*b/std::__gcd(a,b);
}

void solve(){
int x,y,a,b;std::cin >> x >> y >> a >> b;
int lcm = __lcm(x,y);
int st = a/lcm;
int ed = (b+lcm-1)/lcm;
int ans = ed-st+1;
if(st*lcm!=a) --ans;
if(ed*lcm!=b) --ans;
ans = std::max(0,ans);
std::cout << ans << '\n';
}
int main(){
  std::cin.tie(nullptr)->sync_with_stdio(false);

  int t = 1;
  // std::cin >> t;
  for(int ti = 0;ti<t;++ti) {
      solve();
  }

  return 0;
}

3.5 问题 E: 城市公园里的长凳

我的代码

实际上long long就可以存的下了，不过我用的高精度实现的大整数类来写也可以

#include <bits/stdc++.h>
using i64 = long long;
using pii = std::pair<int,int>;
constexpr int N = 1e5+5,M = 1e6+5,INF = 0x3f3f3f3f;

//ctto
typedef long long ll;
typedef long double ld;
typedef std::complex<ld> pt;
const int MOD = 1e9 + 7;
const ld PI = acos(-1.L);

template<class T> struct cplx {
  T x, y;
  cplx() {
    x = 0.0;
    y = 0.0;
  }
  cplx(T nx, T ny = 0) {
    x = nx;
    y = ny;
  }
  cplx operator+(const cplx &c) const {
    return {x + c.x, y + c.y};
  }
  cplx operator-(const cplx &c) const {
    return {x - c.x, y - c.y};
  }
  cplx operator*(const cplx &c) const {
    return {x*c.x - y * c.y, x*c.y + y * c.x};
  }
  cplx& operator*=(const cplx &c) {
    return *this = {x*c.x - y * c.y, x*c.y + y * c.x};
  }
  inline T real() const {
    return x;
  }
  inline T imag() const {
    return y;
  }
  // Only supports right scalar multiplication like p*c
  template<class U> cplx operator*(const U &c) const {
    return {x * c, y * c};
  }
  template<class U> cplx operator/(const U &c) const {
    return {x / c, y / c};
  }
  template<class U> void operator/=(const U &c) {
    x /= c;
    y /= c;
  }
};
#define polar(r,a)  (cplx<ld>){r*cos(a),r*sin(a)}

const int DIG = 9, FDIG = 4;
const int BASE = 1e9, FBASE = 1e4;
typedef cplx<ld> Cplx;


// use mulmod when taking mod by int v and v>2e9
// you can use mod by bigint in that case too
struct BigInt {
  int sgn;
  std::vector<int> a;
  BigInt() : sgn(1) {}
  BigInt(ll v) {
    *this = v;
  }
  BigInt& operator = (ll v) {
    sgn = 1;
    if (v < 0) sgn = -1, v = -v;
    a.clear();
    for (; v > 0; v /= BASE) a.push_back(v % BASE);
    return *this;
  }
  BigInt(const BigInt& other) {
    sgn = other.sgn;
    a = other.a;
  }
  friend void swap(BigInt& a, BigInt& b) {
    std::swap(a.sgn, b.sgn);
    std::swap(a.a, b.a);
  }
  BigInt& operator = (BigInt other) {
    swap(*this, other);
    return *this;
  }
  BigInt(BigInt&& other) : BigInt() {
    swap(*this, other);
  }
  BigInt(const std::string& s) {
    read(s);
  }
  void read(const std::string& s) {
    sgn = 1;
    a.clear();
    int k = 0;
    for (; k < s.size() && (s[k] == '-' || s[k] == '+'); k++)
      if (s[k] == '-') sgn = -sgn;
    for (int i = s.size() - 1; i >= k; i -= DIG) {
      int x = 0;
      for (int j = std::max(k, i - DIG + 1); j <= i; j++) x = x * 10 + s[j] - '0';
      a.push_back(x);
    }
    trim();
  }
  friend std::istream& operator>>(std::istream &in, BigInt &v) {
    std::string s;
    in >> s;
    v.read(s);
    return in;
  }
  friend std::ostream& operator<<(std::ostream &out, const BigInt &v) {
    if (v.sgn == -1 && !v.zero()) out << '-';
    out << (v.a.empty() ? 0 : v.a.back());
    for (int i = (int) v.a.size() - 2; i >= 0; --i)
      out << std::setw(DIG) << std::setfill('0') << v.a[i];
    return out;
  }
  bool operator<(const BigInt &v) const {
    if (sgn != v.sgn) return sgn < v.sgn;
    if (a.size() != v.a.size()) return a.size() * sgn < v.a.size() * v.sgn;
    for (int i = (int)a.size() - 1; i >= 0; i--)
      if (a[i] != v.a[i]) return a[i] * sgn < v.a[i] * sgn;
    return 0;
  }
  bool operator>(const BigInt &v) const {
    return v < *this;
  }
  bool operator<=(const BigInt &v) const {
    return !(v < *this);
  }
  bool operator>=(const BigInt &v) const {
    return !(*this < v);
  }
  bool operator==(const BigInt &v) const {
    return !(*this < v) && !(v < *this);
  }
  bool operator!=(const BigInt &v) const {
    return *this < v || v < *this;
  }
  friend int __cmp(const BigInt& x, const BigInt& y) {
    if (x.a.size() != y.a.size()) return x.a.size() < y.a.size() ? -1 : 1;
    for (int i = (int) x.a.size() - 1; i >= 0; --i) if (x.a[i] != y.a[i])
        return x.a[i] < y.a[i] ? -1 : 1;
    return 0;
  }

  BigInt operator-() const {
    BigInt res = *this;
    if (zero()) return res;
    res.sgn = -sgn;
    return res;
  }

  void __add(const BigInt& v) {
    if (a.size() < v.a.size()) a.resize(v.a.size(), 0);
    for (int i = 0, carry = 0; i < std::max(a.size(), v.a.size()) || carry; ++i) {
      if (i == a.size()) a.push_back(0);
      a[i] += carry + (i < (int) v.a.size() ? v.a[i] : 0);
      carry = a[i] >= BASE;
      if (carry) a[i] -= BASE;
    }
  }

  void __sub(const BigInt& v) {
    for (int i = 0, carry = 0; i < (int) v.a.size() || carry; ++i) {
      a[i] -= carry + (i < (int) v.a.size() ? v.a[i] : 0);
      carry = a[i] < 0;
      if (carry) a[i] += BASE;
    }
    this->trim();
  }

  BigInt operator+=(const BigInt& v) {
    if (sgn == v.sgn) __add(v);
    else if (__cmp(*this, v) >= 0) __sub(v);
    else {
      BigInt vv = v;
      swap(*this, vv);
      __sub(vv);
    }
    return *this;
  }

  BigInt operator-=(const BigInt& v) {
    if (sgn == v.sgn) {
      if (__cmp(*this, v) >= 0) __sub(v);
      else {
        BigInt vv = v;
        swap(*this, vv);
        __sub(vv);
        sgn = -sgn;
      }
    } else __add(v);
    return *this;
  }

  template< typename L, typename R >
  typename std::enable_if <
  std::is_convertible<L, BigInt>::value &&
  std::is_convertible<R, BigInt>::value &&
  std::is_lvalue_reference < R&& >::value,
  BigInt >::type friend operator + (L&& l, R&& r) {
    BigInt result(std::forward<L>(l));
    result += r;
    return result;
  }
  template< typename L, typename R >
  typename std::enable_if <
  std::is_convertible<L, BigInt>::value &&
  std::is_convertible<R, BigInt>::value &&
  std::is_rvalue_reference < R&& >::value,
  BigInt >::type friend operator + (L&& l, R&& r) {
    BigInt result(move(r));
    result += l;
    return result;
  }
  template< typename L, typename R >
  typename std::enable_if <
  std::is_convertible<L, BigInt>::value &&
  std::is_convertible<R, BigInt>::value,
  BigInt >::type friend operator - (L&& l, R&& r) {
    BigInt result(std::forward<L>(l));
    result -= r;
    return result;
  }

  friend std::pair<BigInt, BigInt> divmod(const BigInt& a1, const BigInt& b1) {
    ll norm = BASE / (b1.a.back() + 1);
    BigInt a = a1.abs() * norm, b = b1.abs() * norm, q = 0, r = 0;
    q.a.resize(a.a.size());
    for (int i = a.a.size() - 1; i >= 0; i--) {
      r *= BASE;
      r += a.a[i];
      ll s1 = r.a.size() <= b.a.size() ? 0 : r.a[b.a.size()];
      ll s2 = r.a.size() <= b.a.size() - 1 ? 0 : r.a[b.a.size() - 1];
      ll d = ((ll) BASE * s1 + s2) / b.a.back();
      r -= b * d;
      while (r < 0) r += b, --d;
      q.a[i] = d;
    }
    q.sgn = a1.sgn * b1.sgn;
    r.sgn = a1.sgn;
    q.trim();
    r.trim();
    auto res = std::make_pair(q, r / norm);
    if (res.second < 0) res.second += b1;
    return res;
  }
  BigInt operator/(const BigInt &v) const {
    return divmod(*this, v).first;
  }
  BigInt operator%(const BigInt &v) const {
    return divmod(*this, v).second;
  }
  void operator/=(int v) {
    if (llabs(v) >= BASE) {
      *this /= BigInt(v);
      return;
    }
    if (v < 0) sgn = -sgn, v = -v;
    for (int i = (int) a.size() - 1, rem = 0; i >= 0; --i) {
      ll cur = a[i] + rem * (ll)BASE;
      a[i] = (int) (cur / v);
      rem = (int) (cur % v);
    }
    trim();
  }
  BigInt operator/(int v) const {
    if (llabs(v) >= BASE) return *this / BigInt(v);
    BigInt res = *this;
    res /= v;
    return res;
  }
  void operator/=(const BigInt &v) {
    *this = *this / v;
  }
  ll operator%(ll v) const {
    int m = 0;
    for (int i = a.size() - 1; i >= 0; --i) m = (a[i] + m * (ll) BASE) % v;
    return m * sgn;
  }
  void operator*=(int v) {
    if (llabs(v) >= BASE) {
      *this *= BigInt(v);
      return;
    }
    if (v < 0) sgn = -sgn, v = -v;
    for (int i = 0, carry = 0; i < a.size() || carry; ++i) {
      if (i == a.size()) a.push_back(0);
      ll cur = a[i] * (ll) v + carry;
      carry = (int) (cur / BASE);
      a[i] = (int) (cur % BASE);
    }
    trim();
  }
  BigInt operator*(int v) const {
    if (llabs(v) >= BASE) return *this * BigInt(v);
    BigInt res = *this;
    res *= v;
    return res;
  }

  static std::vector<int> convert_base(const std::vector<int> &a, int old_digits, int new_digits) {
    std::vector<ll> p(std::max(old_digits, new_digits) + 1);
    p[0] = 1;
    for (int i = 1; i < (int) p.size(); i++)
      p[i] = p[i - 1] * 10;
    std::vector<int> res;
    ll cur = 0;
    int cur_digits = 0;
    for (int i = 0; i < (int) a.size(); i++) {
      cur += a[i] * p[cur_digits];
      cur_digits += old_digits;
      while (cur_digits >= new_digits) {
        res.push_back((ll)(cur % p[new_digits]));
        cur /= p[new_digits];
        cur_digits -= new_digits;
      }
    }
    res.push_back((int) cur);
    while (!res.empty() && !res.back())
      res.pop_back();
    return res;
  }

  void fft(std::vector<Cplx>& a, bool invert) const {
    int n = a.size();
    for (int i = 1, j = 0; i < n; ++i) {
      int bit = n / 2;
      for (; j >= bit; bit /= 2) j -= bit;
      j += bit;
      if (i < j) std::swap(a[i], a[j]);
    }
    for (int len = 2; len <= n; len *= 2) {
      ld ang = 2 * PI / len * (invert ? -1 : 1);
      Cplx wlen = polar(1, ang);
      for (int i = 0; i < n; i += len) {
        Cplx w(1);
        for (int j = 0; j < len / 2; ++j) {
          Cplx u = a[i + j], v = a[i + j + len / 2] * w;
          a[i + j] = u + v;
          a[i + j + len / 2] = u - v;
          w *= wlen;
        }
      }
    }
    if (invert) for (int i = 0; i < n; ++i) a[i] /= n;
  }
  void multiply_fft(const std::vector<int> &a, const std::vector<int> &b, std::vector<int> &res) const {
    std::vector<Cplx> fa(a.begin(), a.end()), fb(b.begin(), b.end());
    int n = 1;
    while (n < std::max(a.size(), b.size())) n *= 2;
    n *= 2;
    fa.resize(n);
    fb.resize(n);
    fft(fa, 0);
    fft(fb, 0);
    for (int i = 0; i < n; ++i) fa[i] *= fb[i];
    fft(fa, 1);
    res.resize(n);
    ll carry = 0;
    for (int i = 0; i < n; i++) {
      ll t = (ll)(fa[i].real() + 0.5) + carry;
      carry = t / FBASE;
      res[i] = t % FBASE;
    }
  }
  static inline int rev_incr(int a, int n) {
    int msk = n / 2, cnt = 0;
    while ( a & msk ) {
      cnt++;
      a <<= 1;
    }
    a &= msk - 1;
    a |= msk;
    while ( cnt-- ) a >>= 1;
    return a;
  }
  static std::vector<Cplx> FFT(std::vector<Cplx> v, int dir = 1) {
    Cplx wm, w, u, t;
    int n = v.size();
    std::vector<Cplx> V(n);
    for (int k = 0, a = 0; k < n; ++k, a = rev_incr(a, n))
      V[a] = v[k] / ld(dir > 0 ? 1 : n);
    for (int m = 2; m <= n; m <<= 1) {
      wm = polar( (ld)1, dir * 2 * PI / m );
      for (int k = 0; k < n; k += m) {
        w = 1;
        for (int j = 0; j < m / 2; ++j, w *= wm) {
          u = V[k + j];
          t = w * V[k + j + m / 2];
          V[k + j] = u + t;
          V[k + j + m / 2] = u - t;
        }
      }
    }
    return V;
  }
  static void convolution(const std::vector<int>& a, const std::vector<int>& b, std::vector<int>& c) {
    int sz = a.size() + b.size() - 1;
    int n  = 1 << int(ceil(log2(sz)));
    std::vector<Cplx> av(n, 0), bv(n, 0), cv;
    for (int i = 0; i < a.size(); i++) av[i] = a[i];
    for (int i = 0; i < b.size(); i++) bv[i] = b[i];
    cv = FFT(bv);
    bv = FFT(av);
    for (int i = 0; i < n; i++) av[i] = bv[i] * cv[i];
    cv = FFT(av, -1);
    c.resize(n);
    ll carry = 0;
    for (int i = 0; i < n; i++) {
      ll t = ll(cv[i].real() + 0.5) + carry;
      carry = t / FBASE;
      c[i] = t % FBASE;
    }
  }
  BigInt mul_simple(const BigInt &v) const {
    BigInt res;
    res.sgn = sgn * v.sgn;
    res.a.resize(a.size() + v.a.size());
    for (int i = 0; i < a.size(); i++) if (a[i])
        for (int j = 0, carry = 0; j < v.a.size() || carry; j++) {
          ll cur = res.a[i + j] + (ll) a[i] * (j < v.a.size() ? v.a[j] : 0) + carry;
          carry = (int) (cur / BASE);
          res.a[i + j] = (int) (cur % BASE);
        }
    res.trim();
    return res;
  }
  BigInt mul_fft(const BigInt& v) const {
    BigInt res;
    convolution(convert_base(a, DIG, FDIG), convert_base(v.a, DIG, FDIG), res.a);
    res.a = convert_base(res.a, FDIG, DIG);
    res.trim();
    return res;
  }
  void operator*=(const BigInt &v) {
    *this = *this * v;
  }
  BigInt operator*(const BigInt &v) const {
    if (1LL * a.size() * v.a.size() <= 1000111) return mul_simple(v);
    return mul_fft(v);
  }

  BigInt abs() const {
    BigInt res = *this;
    res.sgn *= res.sgn;
    return res;
  }
  void trim() {
    while (!a.empty() && !a.back()) a.pop_back();
  }
  bool zero() const {
    return a.empty() || (a.size() == 1 && !a[0]);
  }
  friend BigInt gcd(const BigInt &a, const BigInt &b) {
    return b.zero() ? a : gcd(b, a % b);
  }
};
BigInt power(BigInt a, ll k) {
  BigInt ans = 1;
  while (k > 0) {
    if (k & 1) ans *= a;
    a *= a;
    k >>= 1;
  }
  return ans;
}

void solve(){
i64 n;std::cin >> n;
BigInt ans("1");
for(i64 i = 1;i<=5;++i){
ans = ans*(n-i+1)/i;
}
ans = ans*ans*120;
std::cout << ans << '\n';
}
int main(){
  std::cin.tie(nullptr)->sync_with_stdio(false);

  int t = 1;
  // std::cin >> t;
  for(int ti = 0;ti<t;++ti) {
      solve();
  }

  return 0;
}

3.6 问题 F: 虎哥的有向图

我的代码

拓扑排序+dp

#include <bits/stdc++.h>
using i64 = long long;
using pii = std::pair<int,int>;
constexpr int N = 3e5+5,M = 1e6+5,INF = 0x3f3f3f3f;

int n,m;
std::string s;
std::vector<std::vector<int>> edges(N,std::vector<int>());
std::vector<int> indegrees(N,0);
std::vector<std::vector<int>> dp(N,std::vector<int>(30,0));
std::vector<int> v(N,0);

bool topo_sort() {
  std::queue<int> q;
  for(int i = 1;i<=n;++i) {
    if(!indegrees[i]) q.emplace(i);
  }
  int sum = 0;
  while(!q.empty()) {
    auto t = q.front();
    q.pop();
    indegrees[t]=-1;
    ++sum;
    for(int i = 0;i<edges[t].size();++i) {
      int to = edges[t][i];
      for(int j = 1;j<=26;++j) {
        if(v[to]==j) {
          dp[to][j] = std::max(dp[to][j],dp[t][j]+1);
        }else {
          dp[to][j] = std::max(dp[to][j],dp[t][j]);
        }
      }
      if(!--indegrees[to]) {
        q.emplace(to);
      }
    }
  }
  return sum==n;
}
void solve(){
  std::cin >> n >> m >> s;
  for(int i = 0;i<n;++i) {
    v[i+1] = s[i]-'a'+1;
    ++dp[i+1][v[i+1]];
  }
  while(m--) {
    int u,v;std::cin >> u >> v;
    edges[u].emplace_back(v);
    ++indegrees[v];
  }
  if(topo_sort()) {
    int ans = 0;
    for(int i = 1;i<=n;++i) {
      for(int j = 1;j<=26;++j) {
        ans = std::max(ans,dp[i][j]);
      }
    }
    std::cout << ans << '\n';
  }else {
    std::cout << "-1" << '\n';
  }

}
int main(){
  std::cin.tie(nullptr)->sync_with_stdio(false);

  int t = 1;
  // std::cin >> t;
  for(int ti = 0;ti<t;++ti) {
    solve();
  }

  return 0;
}

题解思路及代码

3.7 问题 G: 平安喜乐

我的代码

线段树，需要实现单点修改区间查询，

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
 
#define cc(x) cout << fixed << setprecision(x)
#define int long long
#define ls u<<1
#define rs u<<1|1

template<class Node>
struct SegmentTree {
    const int n, N;
    vector<Node> tr;
    SegmentTree(): n(0) {}
    SegmentTree(int n_): n(n_), N(n * 4 + 10) {
        tr.reserve(N);
        tr.resize(N);
        build(1, 1, n);
    }
 
    void build(int u, int l, int r) {
        tr[u].l = l, tr[u].r = r;
        tr[u].sum = 0; tr[u].tag = 0;
        if (l == r) {
            return;
        }
        int mid = (l + r) >> 1;
        build(ls, l, mid);
        build(rs, mid + 1, r);
    }
 
    void pushup(Node &T, Node L, Node R) {
        T.l = L.l, T.r = R.r;
        T.sum = L.sum + R.sum;
        if (L.resr <= R.resl) {
            T.sum += (L.r - L.R + 1) * (R.L - R.l + 1);
        }
 
        T.resl = L.resl, T.resr = R.resr;
        T.L = (L.L == L.r && L.resr <= R.resl ? R.L : L.L);
        T.R = R.R == R.l && R.resl >= L.resr ? L.R : R.R;
    }
 
    void update(int u, int id, int v) {
        if (tr[u].l == tr[u].r ) {
            tr[u].resl = tr[u].resr = v;
            tr[u].sum = 1;
            tr[u].L = tr[u].R = tr[u].l;
            return;
        }
        int mid = (tr[u].l + tr[u].r) >> 1;
        if (id <= mid) update(ls, id, v);
        else update(rs, id, v);
        pushup(tr[u], tr[ls], tr[rs]);
    }
 
    Node query(int u, int l, int r) {
        if (tr[u].l >= l && tr[u].r <= r) return tr[u];
        int mid = (tr[u].l + tr[u].r) >> 1;
        if(r <= mid) return query(ls, l, r);
        if(l > mid) return   query(rs, l, r);
        Node T;
        pushup(T, query(ls, l, mid), query(rs, mid + 1, r));
        return T;
    }
 
};

struct Node {
    int l, r;
    int L, R, resl, resr;
    int sum, tag;
};

constexpr int N = 2e5 + 10, M = N - 10;

void solve() {
    int n, q;
    cin >> n >> q;
    SegmentTree<Node> tr(n);
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
        tr.update(1, i, a[i]);
    }
 
    while (q --) {
        int op, l, r;
        cin >> op >> l >> r;
        if (op == 2) {
            cout << tr.query(1, l, r).sum << '\n';
        }
        else {
            a[l] = r;
            tr.update(1, l, r);
        }
    }
 
}
 
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
 
    int T = 1;
    // cin >> T;
 
    while (T--) {
        solve();
    }
 
    return 0;
}

迟点再把题解代码放上来 ，因为线段树写得很长，随意不方便直接截图

3.8 问题 H: 夜露死苦

我的代码写得有问题，虽然过了，但是是因为题目数据不够硬核，让我蒙混过去了，这里直接给题解的代码

原文地址：https://blog.csdn.net/Beau_Will/article/details/144096722

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！