专栏文章

题解：P12646 [KOI 2024 Round 1] 升序

___staring__
P12646题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mina8cju
此快照首次捕获于
2025/12/01 23:06
3 个月前
此快照最后确认于
2025/12/01 23:06
3 个月前
查看原文
火箭滑板毛毛虫。
考虑求出 hii=⌊log⁡2ai⌋,exi=[ai−1×2max⁡(hii−hii−1,0)>ai×2max⁡(hii−1−hii,0)]hi_i = \lfloor \log_2 a_i \rfloor, ex_i = [a_{i-1} \times 2^{\max(hi_i - hi_{i-1}, 0)} > a_i \times 2^{\max(hi_{i-1} - hi_i, 0)}]，即 aia_i 二进制下最高位，和若 ai−1,aia_{i-1},a_i 被乘到最高位相同，aia_i 是否需要多乘一步来保证不降。
那么考虑对每个询问从 ll 到 rr 依次加入每个数，维护当前最后一个数被乘之后的最高位 prpr 和答案 smsm，加入 aia_i 时先后令 pr←max⁡(hii,pr+exi),sm←sm+pr−hiipr \larr \max(hi_i, pr+ex_i), sm \larr sm + pr - hi_i。
发现这是历史和状物，于是考虑对右端点扫描线，使用线段树维护左端点对应的答案，(×,+)(\times,+) 矩阵刻画信息。
考虑去掉 max⁡\max，可以发现 prlpr_l 关于 ll 不增，于是用单调栈维护 prlpr_l 的连续段即可，需要维护标记表示栈内 exiex_i 的增量。
复杂度 O(nlog⁡nM⁡)O(n\log{n}\operatorname{M})，其中 O(M⁡)O(\operatorname{M}) 表示单次矩阵乘法的复杂度。
若直接使用 3×33\times3 的矩阵可能难以通过，考虑一些经典卡常技巧，比如循环展开，去掉不变量。
CPP
constexpr int N = 25e4 + 5, M = N << 2;

int n, q;
int arr[N];
vector <array <int, 2>> qry[N];
array <int, 2> stk[N];
LL res[N];

struct mat
{
	LL v1, v2, v3, v4, v5;
	friend mat operator*(mat a, mat b)
	{
		mat c;
		c.v1 = a.v1 * b.v1 + a.v3 * b.v4;
		c.v2 = a.v1 * b.v2 + a.v2 + a.v3 * b.v5;
		c.v3 = a.v1 * b.v3 + a.v3;
		c.v4 = a.v4 * b.v1 + b.v4;
		c.v5 = a.v4 * b.v2 + a.v5 + b.v5;
		return c;
	}
}
val[M], tag[M];
int vis[M];

#define lp (p << 1)
#define rp (p << 1 | 1)
#define m (l + r >> 1)

void update(int p, mat v)
{
	val[p] = val[p] * v;
	tag[p] = vis[p] ? tag[p] * v : v;
	vis[p] = 1;
}

void build(int p = 1, int l = 1, int r = n)
{
	val[p].v3 = tag[p].v1 = 1;
	if (l < r) build(lp, l, m), build(rp, m + 1, r);
}

void modify(int L, int R, mat v, int p = 1, int l = 1, int r = n)
{
	if (r < L || l > R) return;
	if (l >= L && r <= R) return update(p, v);
	if (vis[p]) update(lp, tag[p]), update(rp, tag[p]), vis[p] = 0;
	modify(L, R, v, lp, l, m), modify(L, R, v, rp, m + 1, r);
}

LL query(int k, int p = 1, int l = 1, int r = n)
{
	if (l == r) return val[p].v2;
	if (vis[p]) update(lp, tag[p]), update(rp, tag[p]), vis[p] = 0;
	return k <= m ? query(k, lp, l, m) : query(k, rp, m + 1, r);
}

#undef lp
#undef rp
#undef m

int check(int x, int y)
{
	int t = __lg(y) - __lg(x);
	x <<= max(t, 0), y <<= max(-t, 0);
	return x > y;
}

void mainSolve()
{
	read(n, q);
	for (int i = 1; i <= n; i ++) read(arr[i]);
	for (int i = 1; i <= q; i ++)
	{
		int l, r; read(l, r);
		qry[r].push_back({l, i});
	}
	
	int top = 0, cnt = 0; mat v;
	build(), v.v1 = 1, v.v2 = v.v3 = v.v4 = v.v5 = 0;
	for (int r = 1; r <= n; r ++)
	{
		int h = __lg(arr[r]);
		while (top && stk[top][0] + cnt < h)
		{
			v.v4 = h - stk[top][0] - cnt;
			modify(stk[top - 1][1] + 1, stk[top][1], v);
			v.v4 = 0, --top;
		}
		if (r > 1 && check(arr[r - 1], arr[r]) && top)
			++cnt, v.v4 = 1, modify(1, stk[top][1], v), v.v4 = 0;
		v.v4 = h, modify(r, r, v), v.v4 = 0, stk[++top] = {h - cnt, r};
		v.v2 = 1, v.v5 = -h, modify(1, r, v), v.v2 = v.v5 = 0;
		for (auto [l, i] : qry[r]) res[i] = query(l);
	}
	
	for (int i = 1; i <= q; i ++) write(res[i]);
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...