20260915 每日 2.0 2.5 4.0

No.1110 好听的歌

Note

给你一个长度为 $N$ 的数组 $\set{A}_{i=1}^N$ 表示歌的好感度，对于每一个歌，如果存在一个 $j$，有$A_i - A_j < D$，那么 $A_i$ 对 $A_j$ 有好感，问每个 $A_i$ 的好感数量

$1 \le N \le 2 \times 10^5, 1 \le D \le 10^9$

这是两星？

直接排序后二分，存一个答案，然后再输出就行

namespace XK {
  void solve() {
  	int N, D; in(N, D);
  	V<int> A(N); in(A);
  	auto B = A;
  	map<int, int> mp;
  	sort(all(A));
  	rep(i, N) {
  		auto it = upper_bound(all(A), A[i] - D) - A.begin();
  		mp[A[i]] = it;
  	}
  	rep(i, N) {
  		out(mp[B[i]]);
  	}
  }
};

No.3198 单调查询

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

Note

空数组 $\set{A}$，给定 $Q$ 种操作：

1 x 在 $\set{A}$ 末尾添加 x
2 k 查找现在数组最后 $k$ 位的最大值

$1 \le Q \le 2 \times 10^5$

这是 2.5 ？

直接线段树就行了。。顺便送一个简单的 zkw 线段树

namespace XK {
	struct Segtree {
		int f(int a, int b) {return max(a, b);}
		V<int> s; int n;
		Segtree(int _n) : n(_n), s(2 * _n, - LINF) {}
		void upd(int pos, int val) {
			for(s[pos += n] = val; pos /= 2; ) 
				s[pos] = f(s[pos * 2], s[pos * 2 + 1]);
		}
		int qu(int b, int e) {
			int ra = 0, rb = 0;
			for(b += n, e += n; b < e; b /= 2, e /= 2) {
				if(b % 2) ra = f(ra, s[b ++]);
				if(e % 2) rb = f(s[-- e], rb);
			}
			return f(ra, rb);
		}
	};
  void solve() {
  	int Q; in(Q);
  	Segtree ST(Q);
  	int po = 0;
  	rep(_, Q) {
  		int op; in(op);
  		if(op == 1) {
  			int x; in(x);
  			ST.upd(po ++, x);
  		} else {
  			int k; in(k);
  			out(ST.qu(po - k, po));
  		}
  	}
  }
};

No.1990 糖果盒

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

Note

有一个长度为 $N$ 的数组 $A$，初始全部为 $0$，给定目标数组 $B$。

每次可以选择一个 $i$，要求 $A_i,A_{i+1}$ 奇偶性相同，然后同时令

$A_{i}+1,A_{i+1}+1$

问能否通过若干次操作使 $A=B$。

$2\le N\le 2\times 10^5,\ 0\le B_i\le 10^9$

这是四星？

设 $C_i$ 表示第 $i$ 条相邻边操作的次数，并令两端 $C_0=C_N=0$，那么每个位置满足

$B_i=C_i+C_{i+1}$ 如果出现 $C_i<0$，或者最后 $C_N\ne0$，显然 No

假设 $X_i=(A_i+i)\bmod2$

因为相邻下标奇偶不同，所以当 $A_i,A_{i+1}$ 奇偶相同时，$X_i,X_{i+1}$ 一定不同。

一次操作会让两个 $A$ 都 $+1$，因此对应：

$01\leftrightarrow10$

于是问题转化成：把初始串 $X_i=i\bmod2$

通过相邻交换变成 $Y_i=(B_i+i)\bmod2$ 首先两串中 $1$ 的数量必须相同。

对于第 $i$ 条边，设两边前缀中 $1$ 的数量差为 $d=\left|pre_X-pre_Y\right|$

那么至少需要有 $d$ 个 $1$ 跨过这条边，所以 $C_{i+1}\ge d$

而多余交换成对出现： $01\to10\to01$

所以还需要 $(C_{i+1}-d)\bmod2=0$ 全部满足即可。

namespace XK {
  void solve() {
  	int N; in(N);
  	V<int> B(N), C(N + 1); in(B);
  	rep(i, N) C[i + 1] = B[i] - C[i];
  	if(C[N]) return out("No");
  	rep(i, N) if(C[i] < 0) return out("No");
  	int sx = 0, sy = 0;
  	rep(i, N) sx += i & 1, sy += (B[i] + i) & 1;
  	if(sx != sy) return out("No");
  	int px = 0, py = 0;
  	rep(i, N - 1) {
  		px += i & 1, py += (B[i] + i) & 1;
  		int need = abs(px - py);
  		if(C[i + 1] < need) return out("No");
  		if((C[i + 1] - need) & 1) return out("No");
  	}
  	out("Yes");
  }
};