HDU 暑假多校 2023 第一场

写在前面

补题地址：HDUOJ 题库第 63 页，题号 7275~7286。

以下题号以题库中题号为准。

题目选补，按照个人认为题目难度排序，因为我是菜狗。

打这场看到马娘题目直接整个人兴奋，于是推了 3h 推不出来滚粗了。以为是手玩题没想到是正统博弈论呃呃。早知道去抄个 excrt 板子再去调个线段树就赢了，然而被小北和钻哥迷昏了头脑，输光光！

玩闪耀！优俊少女玩的！

以后每次打开马娘都会想到这天场上的窘态——咿唔噫！！！！！

打完之后头脑发昏把屯的 100 抽都抽了光钻九十抽出了个涛宝呃呃呃呃呃呃呃

输光光！

最害怕的一集，小时候看完这集直接把小北卖了。

7283

简单鸽巢原理。

\(n \times (d - 1) < m\) 成立则 Yes。

7279

幸好学过最小表示法，去抄了份板子直接秒过。

考虑先把每个字符串调整成循环同构中字典序最小的，然后直接对整串哈希。

//知识点：最小表示法 
/*
By:Luckyblock
*/
#include <iostream>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define LL long long
const int kN = 1e5 + 10;
const LL c1 = 114;
const LL c2 = 514;
const LL p1 = 1e9 + 7;
const LL p2 = 1e9 + 9;
//=============================================================
int n, m;
char a[kN];
LL has1[kN], has2[kN];
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
  return f * w;
}
void GetMax(int &fir, int sec) {
  if (sec > fir) fir = sec;
}
void GetMin(int &fir, int sec) {
  if (sec < fir) fir = sec;
}
int MinRep() {
  int i = 0, j = 1, k = 0;
  while (i < m && j < m && k < m) {
    int delta = a[(i + k) % m] - a[(j + k) % m];
    if (delta == 0) {
      ++ k;
      continue ;
    }
    if (delta > 0) i += k + 1;
    else j += k + 1;
    if (i == j) j ++;
    k = 0;
  }
  return std::min(i, j);
}
void Init() {
  n = read(), m = read();
	for (int id = 1; id <= n; ++ id) {
		scanf("%s", a);
    int start = MinRep();
    // printf("--%d\n", start);

    has1[id] = has2[id] = 0;
		for (int i = start, j = 0; j < m; ++ j) {
			int k = (i + j) % m;
			has1[id] = (c1 * has1[id] % p1 + a[k]) % p1;
			has2[id] = (c2 * has2[id] % p2 + a[k]) % p2;
		}
	}
}
bool Query(int x_, int y_) {
	return has1[x_] == has1[y_] && has2[x_] == has2[y_];
}
//=============================================================
int main() {
  int T = read();
  while (T --) {
    Init();
		int q = read();
		while (q --) {
			int x = read(), y = read();
			printf("%s\n", Query(x, y) ? "Yes" : "No");
		}
	}
  return 0;
}

7276

经典题：https://www.luogu.com.cn/problem/P2899。

我直接把 19 年写的题解扔上来。

呃呃现在写居然不会了，wa 了 6 发，我是脑瘫。

题目要求:

给定一棵无根树, 花费 1价值, 覆盖一个点, 并使该点直接相邻的其他点 也被覆盖求将所有点全部覆盖的 最小价值

分析题意:
对于树上的一个节点, 若要被覆盖, 可被其父, 其子覆盖, 或自己覆盖自己覆盖一个节点, 只能影响到与其直接相连的节点, 与其距离1以上的节点 不能被影响, 显然可以DP

对于一棵子树, 若其中所有节点已被覆盖.现考虑子树根节点的父亲的 覆盖情况, 对此子树的影响

1. 若子树的根节点 自覆盖 :
   1. 可不花费额外代价的情况下, 将子树根节点的父亲覆盖,
   2. 也可花费额外1代价, 将子树的根节点的父亲覆盖
      从而覆盖子树的根节点, 并影响其二级子节点
2. 若子树的根节点 未被自己覆盖 :
   即子树的根节点 被其子覆盖
   则 可花费1代价, 将子树的根节点父亲覆盖
   从而覆盖子树的根节点, 并影响其二级子节点

由上, 通过一个节点被覆盖的来源, 可以设计三种状态:
设f[i][0/1/2]表示:当 第i个节点为根的子树全部被覆盖, 第i个节点被 其父亲/自己/儿子 覆盖时, 第i个节点为根的子树内 自己覆盖自己的点的个数

对于以节点i 为根节点的子树, 其上述三个状态的值 可以通过下述方法获得:

1. f[i][0], 即为 sum (min(f[j][1], f[j][2])) (j \in son[i])
2. f[i][1], 将节点i进行自覆盖后, 只能影响到 其直接子节点其直接子节点 的状态可以为以上三种任一
   则有: f[i][1] = 1 + sum (min(f[j][0], f[j][1], f[j][2])) (j \in son[i])
3. f[i][2], 根节点i被其子覆盖
   则其子中 必然有至少一进行了自覆盖.
   其它可进行自覆盖, 也可进行 子覆盖 (但不可进行父覆盖)

   • 先抛开 必须有一进行自覆盖这一限制条件,
     则必然选择 子覆盖和自覆盖 中代价更小的
     即: 若满足f[j][2] - f[j][1] > 0, 选择 自覆盖, 否则选择子覆盖

   • 则必须进行自覆盖的子节点, 选择f[j][2] - f[j][1]最大的 最优
     对于其他的子节点, 当 f[j][2] - f[j][1] > 0时, 选择自覆盖, 否则选择子覆盖

   • 可以设计一比较巧妙的算法实现上述过程:
     先使 f[i][2] = sum(f[j][1]) (j \in son[i]), 同时记录所有f[j][2] - f[j][1]
     之后 对记录的f[j][2] - f[j][1] 进行升序排序
     然后从头到尾进行选择, 若f[j][2] - f[j][1] < 0, 说明 f[j][1] > f[j][2]
     此时使 f[i][2] += f[j][2] - f[j][1], 则可消除之前选择f[j][1]的影响

     当选择了 son - 1个或者 f[j][2] - f[j][1] >=0 时结束选择

好丑啊、、、

//
/*
By:Luckyblock
*/
#include <cmath>
#include <cstdio>
#include <cctype>
#include <vector>
#include <cstring>
#include <algorithm>
#define LL long long
const int kN = 3e5 + 10;
const int kM = kN << 1;
const LL kInf = 1e18 + 2077;
//=============================================================
int n, a[kN];
LL f[kN][4];
int edgenum, head[kN], v[kM], ne[kM];
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0'); 
  return f * w;
}
void Init() {
  edgenum = 0;
  for (int i = 1; i <= n; ++ i) {
    head[i] = 0;
    f[i][0] = f[i][1] = f[i][2] = 0;
  }
}
void Add(int u_, int v_) {
  v[++ edgenum] = v_;
  ne[edgenum] = head[u_];
  head[u_] = edgenum; 
} 
void Dfs(int u_, int fa_) {
  f[u_][1] = a[u_];
  std::vector <LL> son;

  for (int i = head[u_]; i; i = ne[i]) {
    int v_ = v[i];
    if (v_ == fa_) continue;
    Dfs(v_, u_);

    f[u_][0] += std::min(f[v_][1], f[v_][2]);
    f[u_][1] += std::min(f[v_][0], std::min(f[v_][1], f[v_][2]));
    f[u_][2] += f[v_][1], son.push_back(f[v_][2] - f[v_][1]);
  }
  std::sort(son.begin(), son.end());
  if (!son.size()) f[u_][2] = kInf;
  for (int i = 0, sz = son.size(); i < sz - 1; ++ i) {
    if (son[i] < 0) f[u_][2] += son[i];
    else break;
  } 
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  int T = read();
  while (T --) {
    n = read();
    Init();
    for (int i = 1; i <= n; ++ i) a[i] = read();
    for (int i = 1; i < n; ++ i) {
      int u_ = read(), v_ = read();
      Add(u_, v_), Add(v_, u_);
    }
    Dfs(1, 0);
    printf("%lld\n", std::min(f[1][2], f[1][1]));
  }
  return 0;
}

7275

\(T\) 组数据，每组数据给定一棵 \(n\) 个节点的树，\(m\) 次询问。
每次询问给定整数 \(S_a, T_a, S_b, T_b\)，表示有两个人在 0 时刻分别在节点 \(S_a, S_b\) 上，之后分别在路径 \(S_a\leftrightarrow T_a\)，\(S_b\leftrightarrow T_b\) 上以 1 的速度往返。定义当两人在某时刻位于同一个节点上时两人相遇，判断两人能否在某时刻相遇，若可以则求两人第一次相遇的节点。
\(1\le T\le 500\)，\(2\times n,m\le 3\times 10^3\)，不超过 20 组数据使得 \(n\ge 400\)，不超过 20 组数据使得 \(m\ge 400\)。
5S，128MB。

首先有个人尽皆知的结论，对于两条路径 \(S_a\leftrightarrow T_a\)，\(S_b\leftrightarrow T_b\) 的交集，考虑 \(\{ \operatorname{lca}(S_a, T_a), \operatorname{lca}(S_a, T_b), \operatorname{lca}(T_a, S_b), \operatorname{lca}(T_a, T_b) \}\) 中深度最深的两个节点 \(x, y\)：

• \(x\not = y\)：则 \(S_a\leftrightarrow T_a\)，\(S_b\leftrightarrow T_b\) 交集为 \(x\leftrightarrow y\)。
• \(x=y\)：若 \(x\) 的深度比 \(\operatorname{lca}(S_a, T_a)\) 或 \(\operatorname{lca}(S_b, T_b)\) 浅则两条路径没有交集，否则交点为 \(x\)。

然后对于路径 \(S\leftrightarrow T\) 上的某个点 \(x\)，显然从 \(S\) 出发到达 \(x\) 的 时间 \(t\) 肯定满足下列同余方程其中之一：

发现数据范围不大，而且还有特殊性质，\(O(nm)\) 是可以承受的。于是考虑对每次询问先得到两条路径的交，之后枚举路径的交上的结点，得到从 \(S_a\) 和 \(S_b\) 出发到达该点的时间满足的同余方程两两联立成 4 个二元一次同余方程求解即可。

带上求 \(\operatorname{lca}\) 的复杂度，总复杂度上界为 \(O(Tnm\log n)\) 级别。

//
/*
By:Luckyblock
*/
#include <cmath>
#include <cstdio>
#include <cctype>
#include <vector>
#include <cstring>
#include <algorithm>
#define LL long long
const int kN = 5e3 + 10;
const int kM = kN << 1;
const LL kInf = 1e18 + 2077;
//=============================================================
int n, q;
int edgenum, head[kN], v[kM], ne[kM];
int fa[kN], son[kN], dep[kN], size[kN], top[kN];
int next[kN];
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0'); 
  return f * w;
}
void Add(int u_, int v_) {
  v[++ edgenum] = v_;
  ne[edgenum] = head[u_];
  head[u_] = edgenum;
}
void Init() {
  edgenum = 0;
  for (int i = 1; i <= n; ++ i) {
    head[i] = 0;
    fa[i] = son[i] = dep[i] = size[i] = top[i] = 0;
  }
}
namespace Cut {
  void Dfs1(int u_, int fa_) {
    fa[u_] = fa_;
    size[u_] = 1;
    dep[u_] = dep[fa_] + 1;
    for (int i = head[u_]; i; i = ne[i]) {
      int v_ = v[i];
      if (v_ == fa_) continue ;
      Dfs1(v_, u_);
      if (size[v_] > size[son[u_]]) son[u_] = v_;
      size[u_] += size[v_];
    }
  }
  void Dfs2(int u_, int top_) {
    top[u_] = top_;
    if (son[u_]) Dfs2(son[u_], top_);
    for (int i = head[u_]; i; i = ne[i]) {
      int v_ = v[i];
      if (v_ == fa[u_] or v_ == son[u_]) continue ;
      Dfs2(v_, v_);
    }
  }
  int Lca(int u_, int v_) {
    for (; top[u_] != top[v_]; u_ = fa[top[u_]]) {
      if (dep[top[u_]] < dep[top[v_]]) {
        std::swap(u_, v_);
      }
    }
    return dep[u_] < dep[v_] ? u_ : v_;
  }
}
int dis(int s_, int t_) {
  return dep[s_] + dep[t_] - 2 * dep[Cut::Lca(s_, t_)];
}
bool NotIn(int x_, int s_, int t_) {
  return dis(s_, x_) + dis(x_, t_) != dis(s_, t_);
}
LL exgcd(LL a_, LL b_, LL &x_, LL &y_) {
  if (!b_) {
    x_ = 1, y_ = 0;
    return a_;
  }
  LL d = exgcd(b_, a_ % b_, x_, y_);
  LL temp = x_;
  x_ = y_, y_ = temp - a_ / b_ * y_;
  return d;
}
LL lcm(int x_, int y_) {
  LL xx, yy, g = exgcd(x_, y_, xx, yy);
  return x_ / g * y_;
}
void Prepare(int s_, int t_) {
  int lca_ = Cut::Lca(s_, t_);
  for (int i = s_; i != lca_; i = fa[i]) next[i] = fa[i];
  for (int i = t_; i != lca_; i = fa[i]) next[fa[i]] = i;
  next[t_] = 0;
}
LL Calc(LL a1_, LL b1_, LL a2_, LL b2_) {
  LL M = a1_, ans = b1_;
    
  LL A = M, B = a2_, C = (b2_ - ans % B + B) % B, x, y;
  LL g = exgcd(A, B, x, y);
  if (C % g) return kInf;
  x = x * C / g % B, ans += x * M;
  M = lcm(M, B), ans = (ans % M + M) % M;
  
  return ans;
}
void Solve1(int sa_, int ta_, int sb_, int tb_) {
  int lca[5] = {0};
  lca[1] = Cut::Lca(sa_, sb_);
  lca[2] = Cut::Lca(sa_, tb_);
  lca[3] = Cut::Lca(ta_, sb_);
  lca[4] = Cut::Lca(ta_, tb_);
  for (int i = 1; i <= 4; ++ i) {
    for (int j = 1; j < 4; ++ j) {
      if (dep[lca[j]] < dep[lca[j + 1]]) {
        std::swap(lca[j], lca[j + 1]);
      }
    }
  }
  if (NotIn(lca[1], sa_, ta_)) {
    printf("-1\n");
    return ;
  }

  Prepare(lca[1], lca[2]);
  LL da = dis(sa_, ta_), db = dis(sb_, tb_), mintime = kInf, pos = -1;
  for (int i = lca[1]; i; i = next[i]) {
    LL a1 = 2 * da, b1 = dis(sa_, i);
    LL a2 = 2 * da, b2 = 2 * da - b1;
    LL a3 = 2 * db, b3 = dis(sb_, i);
    LL a4 = 2 * db, b4 = 2 * db - b3;
    LL ret1 = Calc(a1, b1, a3, b3);
    if (ret1 < mintime) mintime = ret1, pos = i;
    LL ret2 = Calc(a1, b1, a4, b4);
    if (ret2 < mintime) mintime = ret2, pos = i;
    LL ret3 = Calc(a2, b2, a3, b3);
    if (ret3 < mintime) mintime = ret3, pos = i;
    LL ret4 = Calc(a2, b2, a4, b4);
    if (ret4 < mintime) mintime = ret4, pos = i;
  }
  printf("%lld\n", pos);
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  int T = read();
  while (T --) {
    n = read(), q = read();
    Init();
    for (int i = 1; i < n; ++ i) {
      int u_ = read(), v_ = read();
      Add(u_, v_), Add(v_, u_);
    }
    Cut::Dfs1(1, 0), Cut::Dfs2(1, 1);
    while (q --) {
      int sa = read(), ta = read(), sb = read(), tb = read();
      Solve1(sa, ta, sb, tb);
    }
  }
  return 0;
}

7284

\(T\) 组数据，每组数据给定一长度为 \(n\) 的数列与 \(m\) 次操作，操作为下列两种形式之一：

• 给定整数 \(l, r, x\)，将满足 \(i\in [l ,r]\) 的 \(a_i\) 改为 \(|a_i - x|\)。
• 给定整数 \(l, r\)，求 \(\sum_{i = l}^{r} a_i\)。

特殊性质：保证靠前的操作 1 中的 \(x\) 不大于靠后的操作 1 的。
\(1\le T\le 5\)，\(1\le n,m \le 2\times 10^5\)，\(0\le a_i, x\le 10^7\)。
9S，512MB。

如果 \(a_i\) 均大于 \(x\) 就是普通的区间减，操作后 \(a_i := a_i - x\)。有了特殊性质之后，如果某次操作 1 前 \(a_i<x\)，则之后所有操作 1 均会满足 \(a_i < x\)，操作后 \(a_i:= -a_i + x\)。

于是考虑分别维护两种位置的区间和。

维护两棵线段树，第一棵维护 \(a_i > x\) 的数的区间和，支持区间加，维护区间和与区间最小值。在进行区间修改时如果区间最小值小于 \(x\) 则递归到叶子将这个位置在第一棵树中删除，并加到第二棵树里；第二棵维护 \(a_i < x\) 的区间和，支持区间取反和区间加即可。

在第一棵树中递归到叶子删除位置的操作最多仅会进行 \(n\) 次，则总复杂度 \(O(T(n + m)\log n)\) 级别。

注意实现。通过记录区间内元素个数来实现元素的删除、维护区间和时需要借助区间元素个数、取反标记也会将区间加的标记取反……

tama 的昨天从 9:10 调到 14:30，呃呃呃呃。

//
/*
By:Luckyblock
*/
#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define LL long long
const int kN = 2e5 + 10;
const LL kInf = 9e18 + 2077;
//=============================================================
int n, m, a[kN];
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0'); 
  return f * w;
}
namespace Seg2 {
  #define ls (now_<<1)
  #define rs (now_<<1|1)
  #define mid ((L_+R_)>>1)
  const int kNode = kN << 2;
  LL sum[kNode], tag1[kNode], tag2[kNode];
  int lth[kNode];
  void Pushup(int now_) {
    sum[now_] = sum[ls] + sum[rs];
    lth[now_] = lth[ls] + lth[rs];
  }
  void Pushdown(int now_) {
    if (!tag1[now_] && !tag2[now_]) return;
    if (tag1[now_]) {
      sum[ls] = -sum[ls], sum[rs] = -sum[rs];
      if (lth[ls]) tag1[ls] ^= 1, tag2[ls] = -tag2[ls];
      if (lth[rs]) tag1[rs] ^= 1, tag2[rs] = -tag2[rs];
    }
    if (tag2[now_]) {
      sum[ls] += 1ll * lth[ls] * tag2[now_], sum[rs] += 1ll * lth[rs] * tag2[now_];
      if (lth[ls]) tag2[ls] += tag2[now_];
      if (lth[rs]) tag2[rs] += tag2[now_];
    }
    tag1[now_] = tag2[now_] = 0;
  }
  void Build(int now_, int L_, int R_) {
    if (L_ == R_) {
      sum[now_] = 0;
      tag1[now_] = tag2[now_] = 0;
      lth[now_] = 0;
      return ;
    }
    Build(ls, L_, mid), Build(rs, mid + 1, R_);
    Pushup(now_);
  }
  LL Query1(int now_, int L_, int R_, int l_, int r_) {
    if (!lth[now_]) return 0;
    if (l_ <= L_ && R_ <= r_) return sum[now_];
    Pushdown(now_);
    LL ret = 0;
    if (l_ <= mid && lth[ls]) ret += Query1(ls, L_, mid, l_, r_);
    if (r_ > mid && lth[rs]) ret += Query1(rs, mid + 1, R_, l_, r_);
    Pushup(now_);
    return ret;
  }
  void Modify1(int now_, int L_, int R_, int l_, int r_, int key_) {
    if (!lth[now_]) return ;
    if (l_ <= L_ && R_ <= r_) {
      sum[now_] = -sum[now_] + 1ll * lth[now_] * key_;
      tag2[now_] = -tag2[now_] + 1ll * key_;
      tag1[now_] ^= 1;
      return ;
    }
    Pushdown(now_);
    if (l_ <= mid && lth[ls]) Modify1(ls, L_, mid, l_, r_, key_);
    if (r_ > mid && lth[rs]) Modify1(rs, mid + 1, R_, l_, r_, key_);
    Pushup(now_);
  }
  void Modify2(int now_, int L_, int R_, int pos_, LL val_) {
    if (L_ == R_) {
      sum[now_] = val_;
      lth[now_] = 1;
      return ;
    }
    Pushdown(now_);
    if (pos_ <= mid) Modify2(ls, L_, mid, pos_, val_);
    else Modify2(rs, mid + 1, R_, pos_, val_);
    Pushup(now_);
  }
  #undef ls
  #undef rs
  #undef mid 
}

namespace Seg1 {
  #define ls (now_<<1)
  #define rs (now_<<1|1)
  #define mid ((L_+R_)>>1)
  const int kNode = kN << 2;
  LL sum[kNode], minval[kNode], tag[kNode];
  int lth[kNode], pos[kNode];
  void Pushup(int now_) {
    sum[now_] = sum[ls] + sum[rs];
    minval[now_] = kInf, pos[now_] = 0;
    if (minval[ls] < minval[rs] && lth[ls]) minval[now_] = minval[ls], pos[now_] = pos[ls];
    else if (lth[rs]) minval[now_] = minval[rs], pos[now_] = pos[rs];
    lth[now_] = lth[ls] + lth[rs];
  }
  void Pushdown(int now_) {
    if (!tag[now_]) return;
    if (lth[ls]) {
      sum[ls] += 1ll * lth[ls] * tag[now_]; 
      minval[ls] += tag[now_];
      tag[ls] += tag[now_];
    }
    if (lth[rs]) {
      sum[rs] += 1ll * lth[rs] * tag[now_];
      minval[rs] += tag[now_];
      tag[rs] += tag[now_];
    }
    tag[now_] = 0;
  }
  void Build(int now_, int L_, int R_) {
    if (L_ == R_) {
      sum[now_] = a[L_];
      minval[now_] = a[L_];
      pos[now_] = L_;
      lth[now_] = 1;
      tag[now_] = 0;
      return ;
    }
    Build(ls, L_, mid), Build(rs, mid + 1, R_);
    Pushup(now_);
  }
  LL Query1(int now_, int L_, int R_, int l_, int r_) {
    if (!lth[now_]) return 0;
    if (l_ <= L_ && R_ <= r_) return sum[now_];
    Pushdown(now_);
    LL ret = 0;
    if (l_ <= mid && lth[ls]) ret += Query1(ls, L_, mid, l_, r_);
    if (r_ > mid && lth[rs]) ret += Query1(rs, mid + 1, R_, l_, r_);
    Pushup(now_);
    return ret;
  }
  void Modify1(int now_, int L_, int R_, int l_, int r_, int key_) {
    if (!lth[now_]) return ;
    if (L_ == R_ && minval[now_] <= -key_) {
      lth[now_] = sum[now_] = pos[now_] = 0;
      Seg2::Modify2(1, 1, n, L_, minval[now_]);
      minval[now_] = kInf;
      return ;
    }
    if (l_ <= L_ && R_ <= r_) {
      if (minval[now_] <= -key_) {
        Pushdown(now_);
        if (lth[ls]) Modify1(ls, L_, mid, l_, r_, key_);
        if (lth[rs]) Modify1(rs, mid + 1, R_, l_, r_, key_);
        Pushup(now_);
        return ;
      }
      sum[now_] += 1ll * lth[now_] * key_;
      minval[now_] += key_;
      tag[now_] += key_;
      return ;
    }
    Pushdown(now_);
    if (l_ <= mid && lth[ls]) Modify1(ls, L_, mid, l_, r_, key_);
    if (r_ > mid && lth[rs]) Modify1(rs, mid + 1, R_, l_, r_, key_);
    Pushup(now_);
  }
  #undef ls
  #undef rs
  #undef mid
}
void Init() {
  n = read(), m = read();
  for (int i = 1; i <= n; ++ i) a[i] = read();
  Seg1::Build(1, 1, n), Seg2::Build(1, 1, n);
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  // freopen("2.txt", "w", stdout);
  int T = read();
  while (T --) {
    while (m --) {
      int opt = read(), l = read(), r = read();
      if (opt == 1) {
        int x = read();
        Seg1::Modify1(1, 1, n, l, r, -1ll * x);
        Seg2::Modify1(1, 1, n, l, r, 1ll * x);
      } else {
        LL ans1 = Seg1::Query1(1, 1, n, l, r);
        LL ans2 = Seg2::Query1(1, 1, n, l, r);
        printf("%lld\n", ans1 + ans2);
      }
    }
  }
  return 0;
}

写在最后

学到了什么：

• 及时换题。
• 找数学关系。
• 有的性质一旦满足后就会一直满足。

这场排名垫底咯。

今天 hdu 打不了了，吸吸。

本栏目推荐文章
• 2023年度总结
• CSP-J/S 2023 游记
• Libevent [补档-2023-08-29]
• 本地套接字 [补档-2023-07-24]
• UDP通信 [补档-2023-07-22]
• 多路io复用Select [补档-2023-07-16]
• 多路io复用pool [补档-2023-07-19]
• 多路io复用epoll [补档-2023-07-20]
• socket编程 [补档-2023-07-10]
• OFBiz RCE漏洞复现（CVE-2023-51467）

2023 HDU2023 hdu 题解round 2023 hdu 笔记2023 hdu 7287 2023 hdu hdu hdu-acm 馅饼hdu 老鼠hdu 寝室hdu 3681 hdu