CF1919E

给定长度为 \(n\) 的数列 \(p\)，求有多少个长度为 \(n\) 的数列 \(a\) 满足：\(\forall i\in[1,n],|a_i|=1\)；其前缀和数组排序后恰为数列 \(p\)。\(\sum n\leq 5000\)。

这个题真的抽象，还是先不管了。

Conclusion

• 用折线图观察操作。

• 自定义统一操作生成最终答案。

• 题外话：感觉连续段 dp 也可做？https://www.luogu.com.cn/article/i8kmk5tr

给你一个长为 \(n\) 的非负整数序列 \(a\)，求有多少区间 \([l,r]\) 满足 \(\text{popcount}(\max\limits_{i=l}^r a_i)=\text{popcount}(\min\limits_{i=l}^r a_i)\)。\(1\le n\le 10^6,0\le a_i\le 10^{18}\)。

Conclusion

• Min/Max 分治模型：

所以这个题我们 \(i\) 从 \(mid\) 到 \(l\) 走，动态指针维护 \(p,q\)，然后分别计算这三段的贡献。（对于每个 \(l\) 计算合法的 \(r\)）

具体来说每次枚举的就是 \(l'\)，然后看 \(r'\) 在 \((mid,p],(p,q],(q,r]\) 分别有多少个即可。最麻烦的是第 2 种计算，这个时候我们讨论是哪一个在左边。

void dfs(int l, int r) {
	if(l == r) return ans ++, void();
	int mid = l + r >> 1;
	dfs(l, mid);
	dfs(mid + 1, r);
	pre[mid] = 0; mx[mid] = -1e18, mn[mid] = 1e18;
	for(int i = mid + 1;i <= r; ++i) 
		mx[i] = max(mx[i-1], a[i]), mn[i] = min(mn[i-1], a[i]), 
		pre[i] = pre[i - 1] + (pc(mx[i]) == pc(mn[i]));
	// 我们的桶维护 (p1, p2] 的 pop 个数 
	for(int i = mid, maxn = -1, minn = 1e18, p1 = mid, p2 = mid;i >= l; --i) {
		maxn = max(maxn, a[i]), minn = min(minn, a[i]);
		// p1
		while(p1 < r and maxn >= mx[p1 + 1] and minn <= mn[p1 + 1]) {
			++p1; 
			--cnt1[pc(mx[p1])], --cnt2[pc(mn[p1])];
		}
		// p2
		while(p2 < r and (maxn >= mx[p2 + 1] or minn <= mn[p2 + 1])) {
			++p2; 
			++cnt1[pc(mx[p2])], ++cnt2[pc(mn[p2])];
		}
		// 1. <= p1
		if(pc(maxn) == pc(minn)) ans += p1 - mid;
		// 2. p1 < x <= p2，也就是一边 max 一边 min，比较有难度，分讨 maxmin 在哪边 
		if(maxn >= mx[p2]) // max 在左边 
			ans += cnt2[pc(maxn)]; // min
		else // min 在左边
		 	ans += cnt1[pc(minn)];
		// 3. > p2，max/min 都在右边，左边完全不影响 
		ans += pre[r] - pre[p2]; // 那么就看 max 和 min pc 相等的 r' 个数即可 
	}
	memset(cnt1, 0, sizeof cnt1); memset(cnt2, 0, sizeof cnt2);
}