专栏文章

题解：P12448 [COTS 2025] 观草 / Trava

___staring__
P12448题解参与者 4已保存评论 3

文章操作

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

当前评论
3 条
当前快照
1 份
快照标识符
@min5gs91
此快照首次捕获于
2025/12/01 20:53
3 个月前
此快照最后确认于
2025/12/01 20:53
3 个月前
查看原文
数据结构学傻警告。
这个查询看上去很难做啊，考虑直接维护 sk=∑1≤i≤n−k+1max⁡(ai,ai+1,…,ai+k−1)s_k = \sum_{1 \le i \le n-k+1} \max(a_i,a_{i+1},\dots,a_{i+k-1})，令每个区间的贡献在区间首个最大值处计算。
初始对每个 aia_i，求出最大的 lil_i 使得 ∀j∈[1,li],ai−j+1<ai\forall j \in [1,l_i],a_{i-j+1} \red\lt a_i，和最大的 rir_i 使得 ∀j∈[1,ri],ai+j−1≤ai\forall j \in [1,r_i],a_{i+j-1} \red\le a_i，这一部分可以使用单调栈 O(n)O(n) 解决。于是 aia_i 对区间 [l,r][l,r] 有贡献当且仅当 l∈[i−li+1,i]∧r∈[i,i+ri−1]l \in [i-l_i+1,i] \wedge r \in [i,i+r_i-1]。
考虑对 sks_k 的贡献，不妨假设 li≤ril_i \le r_i，对 k,li,rik,l_i,r_i 的大小关系分讨：
  • 当 0<k≤li0 \lt k \le l_i 时，长 kk 且包含 aia_i 的区间有 kk 个。
  • 当 li<k≤ril_i \lt k \le r_i 时，长 kk 且包含 aia_i 的区间有 lil_i 个。
  • 当 ri<k≤li+ri−1r_i \lt k \le l_i+r_i-1 时，长 kk 且包含 aia_i 的区间有 li+ri−kl_i+r_i-k 个。
  • 当 li+ri−1<k≤nl_i+r_i-1 \lt k \le n 时，长 kk 且包含 aia_i 的区间有 00 个。
发现 sks_k 的值形如 ak×k+bka_k \times k + b_k，操作为区间加单点查，用两棵树状数组分别维护 ak,bka_k,b_k 即可。
修改 aia_i 时，考虑增量 1 会影响到的区间，找到最大的 lil_i 使得 ∀j∈[1,li],ai−j+1<ai\forall j \in [1,l_i],a_{i-j+1} \red< a_i，和最大的 rir_i 使得 ∀j∈[1,ri],ai+j−1<ai\forall j \in [1,r_i],a_{i+j-1} \red< a_i。于是增量 1 对 sks_k 的贡献可以与上文一致计算。
现在考虑修改时如何求出 lil_i，rir_i 是类似的。令 a0=an+1=+∞a_0=a_{n+1}=+\infty，显然这等价于求出最大的 kk 使得 k<i∧ak>aik < i \wedge a_k > a_i。如果修改不是 +1，常用的方法是树套树，但是单次 O(log⁡2n)O(\log^2{n}) 的时间无法承受，实际上可以使用主席树简单处理。
由于不强制在线，考虑求出所有可能出现的值并离散化，记最大值为 mm。考虑按 m→1m \rarr 1 的顺序建立值域关于下标的主席树，结点维护子树内存在的最小下标和最大下标。修改时，直接在 ai+1a_i+1 的版本插入 ii，容易发现这样不影响非 ai+1a_i+1 处版本的查询。
于是做完了，时空复杂度 O(nlog⁡n)−O(nlog⁡n)O(n\log{n})-O(n\log{n})。提交记录。
CPP
void staring::mainSolve()
{
    int n, q;
    read(n, q);
    vector arr(n, 0);
    vector qrr(q, pair {'\0', 0});
	for (int &x : arr) read(x);
    for (auto &[c, x] : qrr) read(c, x), x -= c == '+';
	
    vector brr(arr);
    for (auto [c, x] : qrr)
		if (c == '+') brr.push_back(++arr[x]);
    for (auto [c, x] : qrr) arr[x] -= c == '+';
    rsort(brr), brr.erase(ranges::unique(brr).begin(), brr.end());
    for (int &x : arr) x = brr.end() - rlowb(brr, x) - 1;
    rreve(brr);

    int tot = 0;
    vector rot(brr.size(), 0);
    vector lch((n + q) * 22, 0), rch((n + q) * 22, 0), mnp((n + q) * 22, n), mxp((n + q) * 22, -1);
    #define m (l + r >> 1)
    auto upd = [&] (int &p, int k)
        {return ++tot, lch[tot] = lch[p], rch[tot] = rch[p], mnp[tot] = min(k, mnp[p]), mxp[tot] = max(k, mxp[p]), p = tot;};
    auto mdf = [&] (int k)
    {
        int p = upd(rot[arr[k]], k), l = 0, r = n;
        while (r - l > 1) k < m ? (p = upd(lch[p], k), r = m) : (p = upd(rch[p], k), l = m);
    };
    auto qry = [&] (int k)
    {
        int x = -1, y = n, p = rot[arr[k]], l = 0, r = n;
        while (p) k < m ? (gmin(y, mnp[rch[p]]), p = lch[p], r = m) : (gmax(x, mxp[lch[p]]), p = rch[p], l = m);
        return make_pair(x, y);
    };
    #undef m

    vector kit(n + 1, 0ll), bit(n + 1, 0ll);
    #define lb (-t & t)
    auto add = [&] (int l, int r, LL v)
    {
        for (int t = l; t; t -= lb) kit[t] += v, bit[t] -= l * v;
        for (int t = r; t; t -= lb) bit[t] -= r * v, kit[t] += v;
        for (int t = l + r - 1; t; t -= lb) kit[t] -= v, bit[t] += (l + r) * v;
    };
    auto ask = [&] (int p)
    {
        LL k = 0, b = 0;
        for (int t = p; t <= n; t += lb) k += kit[t], b += bit[t];
        return k * p + b;
    };
    #undef lb
	
    vector crr(viota(0, n) | ranges::to <vector> ());
	rsort(crr, [&] (int x, int y) {return arr[x] < arr[y];});
    for (int j = 0; int i : viota(0, ssize(brr)))
	{
		if (i) rot[i] = rot[i - 1];
		while (j < n && arr[crr[j]] == i) mdf(crr[j ++]);
	}
	
    vector lft(n, -1), rgt(n, n);
	for (int top = 0; int i : viota(0, n))
	{
		while (top && arr[crr[top - 1]] > arr[i]) rgt[crr[--top]] = i;
		if (top) lft[i] = crr[top - 1]; crr[top ++] = i;
	}
	for (int i : viota(0, n))
	{
        tie(lft[i], rgt[i]) = minmax(i - lft[i], rgt[i] - i);
		add(lft[i], rgt[i], brr[arr[i]]);
	}
	
	for (auto [c, k] : qrr)
		if (c == '?') write(ask(k));
		else
		{
            --arr[k];
			auto [l, r] = qry(k);
			tie(l, r) = minmax(k - l, r - k);
			add(l, r, 1), mdf(k);
		}
}

评论

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

正在加载评论...