首页 > 其他分享 >Codeforces Round 881 (Div. 3)--F2

Codeforces Round 881 (Div. 3)--F2

时间:2023-06-22 19:22:04浏览次数:57  
标签:881 minn -- Tree Codeforces int dfn maxn now

F2. Omsk Metro (hard version)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl "\n"
#define int long long
const int N=2e5+5;
const int INF = 0x3f3f3f3f;
// 假设一个区间的最大字段和为 max 最小字段和为 min
// 那么 [min,max]区间的数都可以取到,即都存在对应的子区间。因为点权仅为 1 或 −1
// 一个子区间左右扩张,其值只会加一或者减一,不会跳跃,而初始值为 0
//后面就非常简单了,直接树剖
std::vector<int>edge[N];
struct op{
    char opr;
    int x,y,v;
}a[N];
int val[N],now_n;
//
int n,v[N],sz[N],son[N],dist[N],father[N];
//求子树大小,重儿子,深度,父亲
void Dfs(int x,int fa){
    sz[x]=1;
    for(auto y:edge[x]){
        if(y==fa)continue;
        dist[y]=dist[x]+1;
        father[y]=x;
        Dfs(y,x);
        sz[x]+=sz[y];
        if(sz[y]>sz[son[x]])son[x]=y;
    }
}
int now_dfn,l_dfn[N],r_dfn[N],pos_dfn[N],top[N];
//对于每个点重新编号,同时维护出重链最顶上的点,还有dfn序
//编号顺序就是求在dfn序是加入一个限制,先走重链(从同一点出发子树大的路径)
void DFS(int x,int fa,int tp){
    l_dfn[x]=++now_dfn;pos_dfn[now_dfn]=x;top[x]=tp;
    if(son[x])DFS(son[x],x,tp);
    for(auto y:edge[x]){
        if(y!=fa&&y!=son[x])DFS(y,x,y);
    }
    r_dfn[x]=now_dfn;
}
struct Node{
    int maxn,l_maxn,r_maxn;
    int minn,l_minn,r_minn;
    int sum;
}Tree[N*4];
void pushup(Node &now,Node &l,Node &r){
    now.sum=l.sum+r.sum;
    now.maxn=max(l.r_maxn+r.l_maxn,max(l.maxn,r.maxn));
    now.minn=min(l.r_minn+r.l_minn,min(l.minn,r.minn));
    now.l_maxn=max(l.l_maxn,l.sum+r.l_maxn);
    now.r_maxn=max(r.r_maxn,r.sum+l.r_maxn);
    now.l_minn=min(l.l_minn,l.sum+r.l_minn);
    now.r_minn=min(r.r_minn,r.sum+l.r_minn);
}
void pushup(int now){
    pushup(Tree[now],Tree[now*2],Tree[now*2+1]);
}
void build(int now,int l,int r){
    if(l==r){
        Tree[now].maxn=Tree[now].l_maxn=Tree[now].r_maxn=val[pos_dfn[l]];
        Tree[now].minn=Tree[now].l_minn=Tree[now].r_minn=val[pos_dfn[l]];
        Tree[now].sum=val[pos_dfn[l]];
        return;
    }
    int mid=(l+r)>>1;
    build(now*2,l,mid);
    build(now*2+1,mid+1,r);
    pushup(now);
}
Node qurey(int now,int l,int r,int x,int y){
    if(x<=l&&y>=r)return Tree[now];
    int mid=(l+r)>>1;
    if(y<=mid)return qurey(now*2,l,mid,x,y);
    if(x>mid)return qurey(now*2+1,mid+1,r,x,y);
    Node ans;
    Node ls=qurey(now*2,l,mid,x,y);
    Node rs=qurey(now*2+1,mid+1,r,x,y);
    pushup(ans,ls,rs);
    return ans;
}
Node calc(int x,int y){
    //这里不能用INT_MAX,INT_MIN 会爆
    Node left={-INF,-INF,-INF,INF,INF,INF,0};
    Node right=left;
    while(top[x]!=top[y]){
        if(dist[top[x]]<dist[top[y]])swap(x,y),swap(left,right);
        Node now=qurey(1,1,now_n,l_dfn[top[x]],l_dfn[x]);
        Node t=left;
        //树链向上跳,显然now的dfn序会更小
        pushup(left,now,t);
        x=father[top[x]];
    }
    if(dist[x]<dist[y])swap(x,y),swap(left,right);
    Node t=left;
    Node now=qurey(1,1,now_n,l_dfn[y],l_dfn[x]);
    pushup(left,now,t);
    swap(left.r_maxn,left.l_maxn);
    swap(left.r_minn,left.l_minn);
    Node ans;
    pushup(ans,left,right);
    return ans;
}
signed main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int T=1;cin>>T;
    while(T--){
        cin>>n;
        for(int i=0;i<=n+5;i++)edge[i].clear(),son[i]=0;
        now_n=1;val[1]=1;now_dfn=0;dist[1]=0;
        for(int i=1;i<=n;i++){
            cin>>a[i].opr;
            if(a[i].opr=='+'){
                cin>>a[i].y>>a[i].v;
                edge[a[i].y].push_back(++now_n);
                val[now_n]=a[i].v;
            }
            else cin>>a[i].x>>a[i].y>>a[i].v;
        }
        Dfs(1,1);DFS(1,1,1);
        build(1,1,now_n);
        for(int i=1;i<=n;i++){
            if(a[i].opr=='+')continue;
            int x=a[i].x,y=a[i].y,v=a[i].v;
            if(x==y){
                if(v==0||v==val[x])cout<<"YES"<<endl;
                else cout<<"NO"<<endl;
                continue;
            }
            Node ans=calc(x,y);
            ans.minn=min(0ll,ans.minn);
            ans.maxn=max(0ll,ans.maxn);
            if(v>=ans.minn&&v<=ans.maxn)cout<<"YES"<<endl;
            else cout<<"NO"<<endl;
        }
    }       
    return 0;
}

 

标签:881,minn,--,Tree,Codeforces,int,dfn,maxn,now
From: https://www.cnblogs.com/zhujio/p/17498188.html

相关文章

  • MacBook 搭建python开发环境
    转载请注明来源:http://www.eword.name/Author:ewordEmail:[email protected]专题目录MacBook搭建python开发环境一、需要安装的软件安装Python安装pip安装Virtualenv安装VSCodeVSCode安装Python扩展插件安装PyCharm二、IDE搭配VSCode+Python+pip+Virtuale......
  • linux中用crontab定时任务启动jar无效的问题
    原文链接:https://blog.csdn.net/for_the_time_begin/article/details/113940508问题:使用linux系统中的定时任务执行jar包,但是经过测试发现一只不能正常执行,发现定时任务crontab是正常运行的,因为再写一个测试用的定时任务指定时间在指定的目录位置下生成一个文件,或者向文件中追......
  • 李火旺
    关键人物:1.李火旺普通的高中生,是一名精神病人,心素2.白灵淼3.丹阳子李火旺的师傅,癞子头,脸丑,地包天,不识字,修丹道剑道4.杨娜李火旺现实世界的女朋友阵营:清风观(丹阳子)......
  • 部署zabbix5
    部署zabbix5.0前言检查防火墙是否关闭vim/etc/selinux/configSELINUX=disabled内存4G为好配置好阿里yum源实验步骤获取zabbix的下载源rpm-Uvhhttps://mirrors.aliyun.com/zabbix/zabbix/5.0/rhel/7/x86_64/zabbix-release-5.0-1.el7.noarch.rpm更换za......
  • 【雕爷学编程】Arduino动手做(119)---JQ6500语音模块
    37款传感器与执行器的提法,在网络上广泛流传,其实Arduino能够兼容的传感器模块肯定是不止这37种的。鉴于本人手头积累了一些传感器和执行器模块,依照实践出真知(一定要动手做)的理念,以学习和交流为目的,这里准备逐一动手尝试系列实验,不管成功(程序走通)与否,都会记录下来—小小的进步或是搞......
  • java中java.util.Date和java.sql.Date之间的转换
    1、util.Date和sql.Date之间的关系我们来看下java.sql.Date的源码packagejava.sql;importjava.time.Instant;importjava.time.LocalDate;publicclassDateextendsjava.util.Date{}从以上源码可以看出,sql.Date是util.Date的子类2、util.Date的构造方法以下是ja......
  • Nginx 解析漏洞复现、利用
    1、漏洞复现用vulhub复现该漏洞vubhub环境搭建:https://blog.csdn.net/weixin_59679023/article/details/123739030nginx解析漏洞:https://vulhub.org/#/environments/nginx/nginx_parsing_vulnerability/打开终端输入:cdvulhub/nginx/nginx_parsing_vulnerability/sudodocker-co......
  • pg数据类型及数据类型转换
    数字类型:字符类型:时间日期类型:时间日期数据型支持的操符有、减、乘、除,下面举例说明:时间/日期类型常用函数:布尔类型:网络地址类型:当有存储IP地址需求的业务场时,对于PostgreSQL并不很悉的开发者可能会使用字符类型存储,实际上PostgreSQL提供用于存储IPv4......
  • crontab不能执行的原因
    最近经常碰到关于crontab不能执行的,初步总结了有以下几个原因:第一,脚本的原因:大多数情况下,我们要相信科学,相信计算机,不是有鬼,就是我们的脚本的问题,这种问题导致crontab不能执行的概率占到70%以上。因为程序执行到某一步导致crontab终止执行,我就碰到一次在迁移代码的时候将数据库连......
  • 基于python的 Web 开发框架学习笔记
    转载请注明来源:http://www.eword.name/Author:ewordEmail:[email protected]专题目录基于python的Web开发框架学习笔记详细记录Eword的python入门过程IDE环境推荐#【推荐】VSCode+Python+pip+Virtualenv或#【可选】PyCharm+Python+pip+Virtualenv......