基础

模类

  1. constexpr int P = 1000000007;
  2. // assume -P <= x < 2P
  3. int norm(int x) { if (x < 0) x += P; else if (x >= P) x -= P; return x; }
  4. // 快速幂
  5. template <class T> T power(T a, int b) { T res = 1; for (; b; b /= 2, a *= a) { if (b % 2) { res *= a; } } return res; }
  6. struct Mint {
  7.   int x;
  8.   Mint(int x = 0) : x(norm(x)) {}
  9.   int val() const { return x; }
  10.   Mint operator-() const { return Mint(norm(P - x)); }
  11.   Mint inv() const { assert(x != 0); return power(*this, P - 2); }
  12.   Mint &operator*=(const Mint &rhs) { x = ll(x) * rhs.x % P; return *this; }
  13.   Mint &operator+=(const Mint &rhs) { x = norm(x + rhs.x); return *this; }
  14.   Mint &operator-=(const Mint &rhs) { x = norm(x - rhs.x); return *this; }
  15.   Mint &operator/=(const Mint &rhs) { return *this *= rhs.inv(); }
  16.   friend Mint operator*(const Mint &lhs, const Mint &rhs) { Mint res = lhs; res *= rhs; return res; }
  17.   friend Mint operator+(const Mint &lhs, const Mint &rhs) { Mint res = lhs; res += rhs; return res; }
  18.   friend Mint operator-(const Mint &lhs, const Mint &rhs) { Mint res = lhs; res -= rhs; return res; }
  19.   friend Mint operator/(const Mint &lhs, const Mint &rhs) { Mint res = lhs; res /= rhs; return res; }
  20. };
  22. // 阶乘和逆元
  23. Mint fac[N], inv[N];
  24. inline Mint C(int A, int B){ return fac[A] * inv[B] * inv[A - B]; }
  25. /*** main ***/
  26. n = N - 1;
  27. fac[0] = 1;
  28. rep(i,1,n) fac[i] = fac[i-1] * i;
  29. inv[n] = fac[n].inv();
  30. per(i,n-1,0) inv[i] = inv[i+1] * (i + 1);
  31. /*** endmain ***/

数据结构

树状数组

  1. template <typename T>
  2. struct Fenwick {
  3.   const int n;
  4.   vector<T> a;
  5.   Fenwick(int n): n(n), a(n + 1) {}
  6.   void add(int x, T v){
  7.     for(int i = x; i <= n; i += i & -i) a[i] += v;
  8.   }
  9.   T sum(int x) {
  10.     T rs = 0;
  11.     for(int i = x; i; i -= i & -i) {
  12.       rs += a[i];
  13.     }
  14.     return rs;
  15.   }
  16.   T rangeSum(int l, int r) {
  17.     if(l > r) return 0;
  18.     return sum(r) - sum(l - 1);
  19.   }
  20. };

线段树

http://oj.daimayuan.top/problem/813

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define dbg(x...) do { cout << "\033[32;1m" << #x <<" -> "; err(x); } while (0)
  4. void err() { cout << "\033[39;0m" << endl; }
  5. template<class T, class... Ts> void err(const T& arg,const Ts&... args) { cout << arg << " "; err(args...); }
  6. #define rep(i,j,k) for(int i=int(j);i<=int(k);i++)
  7. #define per(i,j,k) for(int i=int(j);i>=int(k);i--)
  8. typedef long long ll;
  9. const int inf = 1E9;
  11. template<class Info, class Merge = plus<Info>>
  12. struct SegTree{
  13.   const int n;
  14.   const Merge merge;
  15.   vector<Info> info;
  16.   SegTree(int n): n(n), merge(Merge()), info(4 * n) {}
  17.   SegTree(int n, vector<Info>& init): SegTree(n) {
  18.     function<void(int,int,int)> build = [&](int p, int l, int r) {
  19.       if(l == r) {
  20.         info[p] = init[l];
  21.         return;
  22.       }
  23.       int m = (l + r) / 2;
  24.       build(2 * p, l, m);
  25.       build(2 * p + 1, m + 1, r);
  26.       pull(p);
  27.     };
  28.     build(1, 1, n);
  29.   }
  31.   void pull(int p) {
  32.     info[p] = merge(info[2 * p], info[2 * p + 1]);
  33.   }
  35.   void modify(int p, int l, int r, int x, const Info &v) {
  36.     if(l == r) {
  37.       info[p] = v;
  38.       return;
  39.     }
  40.     int m = (l + r) / 2;
  41.     if(x <= m) modify(p * 2, l, m, x, v);
  42.     else modify(2 * p + 1, m + 1, r, x, v);
  43.     pull(p);
  44.   }
  46.   void modify(int p, const Info &v) {
  47.     modify(1, 1, n, p, v);
  48.   }
  50.   Info rangeQuery(int p, int l, int r, int x, int y) {
  51.     if(l > y || r < x) {
  52.       return Info();
  53.     }
  54.     if(l >= x && r <= y) return info[p];
  55.     int m = (l + r) / 2;
  56.     return merge(rangeQuery(p * 2, l, m, x, y), rangeQuery(p * 2 + 1, m + 1, r, x, y));
  57.   }
  59.   Info rangeQuery(int l, int r) {
  60.     return rangeQuery(1, 1, n, l, r);
  61.   }
  62. };
  64. // 创建结点信息、*运算
  65. struct Node {
  66.   int ls, rs, mx, sum;
  67.   Node() {
  68.     Node(-inf);
  69.     sum = 0;
  70.   }
  71.   Node(int val):ls(val),rs(val),mx(val),sum(val){}
  72. };
  73. Node operator * (const Node &l, const Node &r) {
  74.   Node t;
  75.   t.sum = l.sum + r.sum;
  76.   t.mx = max(l.rs + r.ls, max(l.mx, r.mx));
  77.   t.ls = max(l.ls, l.sum + r.ls);
  78.   t.rs = max(r.rs, r.sum + l.rs);
  79.   return t;
  80. }
  81. struct Mul {
  82.   Node operator () (const Node &l, const Node &r) const {
  83.     return l * r;
  84.   }
  85. };
  87. int main() {
  88.   ios::sync_with_stdio(false); cin.tie(nullptr);
  89.   int n, m;
  90.   cin >> n >> m;
  91.   vector<Node> a(n + 1);
  92.   rep(i,1,n) {
  93.     int x; cin >> x;
  94.     a[i] = Node(x);
  95.   }
  97.   SegTree<Node, Mul> seg(n, a);
  98.   while (m--)
  99.   {
  100.     int o, x, y;
  101.     cin >> o >> x >> y;
  102.     if(o == 1) {
  103.       if(x > y) swap(x, y);
  104.       cout << seg.rangeQuery(x, y).mx << endl;
  105.     } else {
  106.       seg.modify(x, Node(y));
  107.     }
  108.   }
  109.   return 0;
  110. }