20260923 每日 2.0 2.5 4.0

No.2409 Strange Werewolves

是0的那个必须留到最后，所以剩下的选法就是 $(X + Y - Z - 1)!$

然后考虑剩下的 Z 个和最后剩下那个，选法就是 $\binom{X}{Z} \times Y$

当然如果不是 W 是 0 的话，swap 一下就行

No.1596 Distance Sum in 2D Plane （2D平面上距离和）

首先是经典的如何算无约束下的结果，就是从 2N 中方案里选择 N 步向上，也就是 $\binom{2N}{N} \times 2N$ 元。

然后遇到约束的时候考虑，经过该路径的路径价格 -= 1 就可以了

横着的就是 $\binom{x+y}{x} \times \binom{2 N -x-y-1}{N-y}$

竖着的就是 $\binom{x+y}{x} \times \binom{2 N -x-y-1}{N-x}$

No.2340 Triple Tree Query(EASY)

https://yukicoder.me/problems/no/2340

考虑简化成区间修改 + 单点查询的问题，设运算 $F(x, c, d) := cx + d$

满足结合律且有单位元，所以可以用线段树来维护，于是考虑如何维护后代区间关系。

因为 K = 1，于是可以考虑子代和父亲单独维护一个区间，使用时间计数即可。

在计数过程中，搜索顺序是先搜到一端的叶子再搜另一端，于是有搜索：

auto dfs = [&](this auto && dfs, int u, int f) -> void {
  		fa[u] = f;
  		L[u] = tt + 1;
  		for(auto v : e[u]) if(v != f) {
				pos[v] = ++ tt;  			
  		}
  		H[u] = tt;
  		for(auto v : e[u]) if(v != f) {
  			dfs(v, u);
  		}
  		R[u] = tt;
  	};

H[i] 维护的是 K = 1 时候的可选集合， R[i] 则是子树时的。

这题也可以使用 BFS 来做，但是要用栈。

后续的区间修改单点查询不一定非要使用Lazy Segtree，可以考虑用 Dual Segt

namespace XK {

template <typename T>
struct dual_segment_tree{
  int N;
  vector<T> ST;
  function<T(T, T)> f;
  T E;
  dual_segment_tree(int n, function<T(T, T)> f, T E): f(f), E(E){
    N = 1;
    while (N < n){
      N *= 2;
    }
    ST = vector<T>(N * 2 - 1, E);
  }
  void push(int i){
    if (i < N - 1){
      ST[i * 2 + 1] = f(ST[i * 2 + 1], ST[i]);
      ST[i * 2 + 2] = f(ST[i * 2 + 2], ST[i]);
      ST[i] = E;
    }
  }
  T operator [](int k){
    int v = 0;
    for (int i = N / 2; i >= 1; i >>= 1){
      push(v);
      if ((k & i) == 0){
        v = v * 2 + 1;
      } else {
        v = v * 2 + 2;
      }
    }
    return ST[v];
  }
  void range_apply(int L, int R, T x, int i, int l, int r){
    if (r <= L || R <= l){
    } else if (L <= l && r <= R){
      ST[i] = f(ST[i], x);
    } else {
      push(i);
      int m = (l + r) / 2;
      range_apply(L, R, x, i * 2 + 1, l, m);
      range_apply(L, R, x, i * 2 + 2, m, r);
    }
  }
  void range_apply(int L, int R, T x){
    range_apply(L, R, x, 0, 0, N);
  }
};
const ll mod = 998244353;
struct mm {
};

using pmm = pair<mm, mm>;

pmm comp(pmm a, pmm b) {
	return {
		a.fst * b.fst,
		a.snd * b.fst + b.snd
	};
}

  void solve() {
  	int N, Q; cin >> N >> Q;
  	V<V<int>> e(N);
  	rep(i, N - 1) {
  		int u, v; cin >> u >> v; -- u, -- v;
  		e[u].pb(v), e[v].pb(u);
  	}
  	V<int> X(N);
  	rep(i, N) cin >> X[i];

  	V<int> pos(N), fa(N, -1), L(N), R(N), H(N);
  	pos[0] = 0; 
  	int tt = 0;
  	auto dfs = [&](this auto && dfs, int u, int f) -> void {
  		fa[u] = f;
  		L[u] = tt + 1;
  		for(auto v : e[u]) if(v != f) {
				pos[v] = ++ tt;  			
  		}
  		H[u] = tt;
  		for(auto v : e[u]) if(v != f) {
  			dfs(v, u);
  		}
  		R[u] = tt;
  	};
  	dfs(0, -1);

  	dual_segment_tree<pmm> Segt(N, comp, pmm{mm(1), mm(0)});

  	rep(_, Q) {
  		int op; cin >> op;
  		if(op == 1) {
  			int V; cin >> V; -- V;
  			auto [a, b] = Segt[pos[V]];
  			cout << (a * X[V] + b).x << '\n';

  		} else if(op == 2) {
  			int V, K, C, D; cin >> V >> K >> C >> D; -- V;
  			pmm up{mm(C), mm(D)};
  			Segt.range_apply(pos[V], pos[V] + 1, up);
  			if(fa[V] != -1) Segt.range_apply(pos[fa[V]], pos[fa[V]] + 1, up);
  			if(L[V] <= H[V]) Segt.range_apply(L[V], H[V] + 1, up);

  		} else {
  			int V, C, D; cin >> V >> C >> D; -- V;
  			pmm up{mm(C), mm(D)};
  			Segt.range_apply(pos[V], pos[V] + 1, up);
  			if(L[V] <= R[V]) Segt.range_apply(L[V], R[V] + 1, up);
  		}
  	}
  }
};