首页 > 其他分享 >CF1843F2 题解

CF1843F2 题解

时间:2024-07-25 21:55:52浏览次数:12  
标签:return int 题解 top CF1843F2 dfn ans qry

题面

注意到边权只有 \(1,-1\),所以有结论:存在值为 \(v\) 的子段当且仅当 \(v\in[\) 最小子段和,最大子段和 \(]\)。

证明:因为移动区间端点,区间和变化连续(+1/-1),从最小子段移动到最大子段,子段和一定经过 \(v\),所以得证。

于是只要树剖维护最小最大子段和即可。

和线段树上维护的数据一样,查询时维护两侧的四个数据(Lmax,Rmax,max,sum),转移时和从线段树上查询出的四个数据合并。


注意两侧的转移是相反的(一个向上一个向下,在加号不同侧)。

求最小子段和等于求 原序列全部取负数 的 最大子段和 的 相反数。


#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

struct node
{
    int l, m, r, s;
    node operator+(node x)
    {
        return {max(l, s + x.l), max({m, x.m, r + x.l}), max(x.r, x.s + r), s + x.s};
    }
    node rev() {swap(l, r); return *this;}
};

const int N = 2e5 + 5;

int b[N], c[N];
vector<int> e[N];
int dfn[N], son[N], sz[N], dep[N], top[N], fa[N], id[N], ts;

struct sgt
{
    node a[N << 2];
    void pushup(int x)
    {
        a[x] = a[x << 1] + a[x << 1 | 1];
    }
    void build(int x, int l, int r, int b[])
    {
        if(l == r)
        {
            a[x] = {max(0, b[id[l]]), max(0, b[id[l]]), max(0, b[id[l]]), b[id[l]]};
            return;
        }
        int mid = l + r >> 1;
        build(x << 1, l, mid, b);
        build(x << 1 | 1, mid + 1, r, b);
        pushup(x);
    }
    node qry(int ql, int qr, int l, int r, int x)
    {
        if(ql <= l && r <= qr) return a[x];
        int mid = l + r >> 1;
        if(mid < ql) return qry(ql, qr, mid + 1, r, x << 1 | 1);
        if(mid >= qr) return qry(ql, qr, l, mid, x << 1);
        return qry(ql, qr, l, mid, x << 1) + qry(ql, qr, mid + 1, r, x << 1 | 1);
    }
}t, p;

void dfs1(int x, int fa)
{
    son[x] = 0;
    ::fa[x] = fa;
    dep[x] = dep[fa] + 1;
    sz[x] = 1;
    for(int i : e[x])
    {
        if(i == fa) continue;
        dfs1(i, x);
        sz[x] += sz[i];
        if(sz[i] > sz[son[x]]) son[x] = i;
    }
}

void dfs2(int x, int tp)
{
    top[x] = tp;
    dfn[x] = ++ts;
    id[ts] = x;
    if(son[x]) dfs2(son[x], tp);
    for(int i : e[x])
        if(i != fa[x] && i != son[x])
            dfs2(i, i);
}

int n;

int qry(int x, int y, sgt &t)
{
    node ans[2] = {{0, 0, 0, 0}, {0, 0, 0, 0}};
    int f = 0;
    while(top[x] != top[y])
    {
        if(dep[top[x]] < dep[top[y]]) swap(x, y), f ^= 1;
        if(f == 0) ans[f] = ans[f] + t.qry(dfn[top[x]], dfn[x], 1, n, 1).rev();
        else ans[f] = t.qry(dfn[top[x]], dfn[x], 1, n, 1) + ans[f];
        x = fa[top[x]];
    }
    if(dep[x] < dep[y]) swap(x, y), f ^= 1;
    if(f == 0) ans[f] = ans[f] + t.qry(dfn[y], dfn[x], 1, n, 1).rev();
    else ans[f] = t.qry(dfn[y], dfn[x], 1, n, 1) + ans[f];
    return (ans[0] + ans[1]).m;
}

struct QU{int x, y, k;}qu[N];
int cntq;

void solve()
{
    int q;cin >> q;
    n = 1;cntq = 0;ts = 0;
    b[1] = 1;c[1] = -1;
    e[1].clear();
    for(int i = 1; i <= q; i ++)
    {
        char op;
        int x, y, k;
        cin >> op >> x >> y;
        if(op == '+')
        {
            n ++;
            e[n].clear();
            e[x].push_back(n);
            e[n].push_back(x);
            b[n] = y;
            c[n] = -y;
        }
        else
        {
            cin >> k;
            qu[++cntq] = {x, y, k};
        }
    }
    dfs1(1, 0);
    dfs2(1, 1);
    t.build(1, 1, n, b);
    p.build(1, 1, n, c);
    for(int i = 1; i <= cntq; i ++)
    {
        if(qry(qu[i].x, qu[i].y, t) >= qu[i].k && -qry(qu[i].x, qu[i].y, p) <= qu[i].k) cout << "YES\n";
        else cout << "NO\n";
    }
}

signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    int t;cin >> t;while(t --) solve();

    return 0;
}

标签:return,int,题解,top,CF1843F2,dfn,ans,qry
From: https://www.cnblogs.com/adam01/p/18324224

相关文章

  • CF440D 题解
    题面注意到划分完这棵树以后,每条连通块之间的边的一端一定相同,且是大小为\(k\)的连通块。于是考虑这个连通块的最高点,设\(f(i,j)\)为\(i\)点所在连通块大小为\(j\)时所需的最小边数。令\(f'(i)\)为原来的\(f(i)\)。对于\(i\)的每个\(s\inson(i)\),枚举从\(s\)......
  • CF56E 题解
    题面设骨牌\(i\)倒下之后会连带压倒\([i+1,r_i]\)的骨牌,那么有\(z_i=\max_{j=i+1}^{r_i}z_j+(j-i)\)考虑线段树优化dp,但是\((j-i)\)不好维护,所以套路地修改式子,得到:\(z_i+i=\max_{j=i+1}^{r_i}(z_j+j)\)所以线段树维护\(z_i+i\)的区间最大值即可,\(r_i\)可以二分求......
  • CF86D 题解
    题面看起来线段树之类的不好维护,但是移动区间的增量很好求,数据范围也能过,那么直接莫队就行了。设加入或删除了值\(x\),设原来区间内有\(cnt_x\)个,现在有\(cnt'_x\)个,那么增量就是\(x((cnt'_x)^2-(cnt_x)^2)\),直接求就好了。复杂度\(O(t\sqrtn)\)。#include<bits/stdc+......
  • CF567E 题解
    题面考虑如何一条边是必经之路:设\(cntl_i\)为从\(s\)到\(i\)走最短路的方案数,\(cntr_i\)为从\(i\)到\(t\)最短路方案数。由乘法原理,如果对于边\(e_i=(u,v)\),\(cnt_t=cnt_u\timescntr_v\),则\(e_i\)是最短路上的必经边,输出Yes即可。如果\(cnt_u\timescntr_v=0......
  • 【题解】Solution Set - 杂题选讲「刘君实」
    https://www.becoder.com.cn/contest/5423「HNOI2012」集合选数感觉差不多会。7/25sh杂题听课情况NOI2018冒泡排序【40】几乎不会麦田里的守望者【40】打表找规律、最后dp不太理解星空列车【40】完全不会WereYouLast:知道怎么做,但是不知道为什么是对的A......
  • CF467E 题解
    题面给出这种限制,我们只能4个4个考虑。令\(f_i\)为考虑到\(a_i\),最长的\(b\)序列长\(4f_i\)。令\(mx_i\)为以\(a_i\)结尾的最短连续子序列包含\(x\y\x\y\)的(不一定连续的)结构的左端点。于是有\(f_i=\max_{j=1}^{mx_i-1}f_j+4\)。用前缀和优化:\(g_i=\max......
  • CF594A 题解
    题面来个不一样的证明。根据样例,我们可以有一个直觉:两点之间一定距离\(\fracn2\),答案为这样的点对之间\(\Deltax\)的最小值。直接交上去,发现这是对的。为什么呢?先证明上界:先手可以让答案小于等于两点距离\(\fracn2\)点对的\(\Deltax\)的最小值。这是容易的:先手只......
  • 题解:Codeforces Round 961 (Div. 2) B1&B2
    本题含有B1和B2两个难度版本。由于关系相近,我把他们放在同一篇博客中,可自行选择观看B1.Bouquet(EasyVersion)timelimitpertest:1.5secondsmemorylimitpertest:512megabytesinput:standardinputoutput:standardoutputThisistheeasyversionoftheprobl......
  • CF568C New Language 题解
    Description将\(\texttt{a}\sim\texttt{a}+l-1\)这\(l\)个字符分成\(\texttt{V,C}\)两个集合。你需要构造一个长度为\(n\)且满足\(m\)个限制且不小于另一个长度为\(n\)的字符串\(s\)的最小字符串。每一个限制为若字符串的第\(p_1\)个位置上的字符\(\in......
  • CF22E 题解
    题面注意到题目给的图为基环树森林。因为一个(\(n>1\))的强连通图每个点都要有出度和入度,所以:对于每个基环树,叶子结点是没有入度的,所以一定要有一条从环上出发的路径经过这个点。对于基环树的环,注意到它缩点后没有出度,所以一定要有一条出边。注意到叶子结点的需求和根节点相反,......