首页 > 其他分享 >2023NOIP A层联测26 T3 tour

2023NOIP A层联测26 T3 tour

时间:2023-11-09 09:33:04浏览次数:40  
标签:26 int tree T3 tot mid tour maxn lca

2023NOIP A层联测26 T3 tour

有意思的树上主席树。

思路

首先考虑一个点 \(p\) 能计入答案的情况,就是 \(dis(x,p)-a_p \ge a_p\)。 我们把 \(x \to y\) 的路径拆成 \(x \to lca,lca \to y\) 两条。

记录一个点 \(x\) 到根路径上的前缀和为 \(s_x\),对于两条路径,我们分类讨论:

第一条,合法条件为 \(s_x-s_p \ge a_p\),也就是 \(s_p+a_p \le s_x\)。左边的是一个关于 \(p\) 的式子,我们把它放到某个数据结构里面,查询一条链上小于等于给定值的值的个数,如果树给定,这显然是可以通过主席树来做的。

具体来说,每个点继承它父亲的版本,最后把两个版本一减就好了。

第二条,我们记录 lca 的父亲为 \(z\),那么合法条件为 \(s_x-s_z+s_p-s_{lca}-a_p \ge a_p\),也就是 \(2 \times a_p-s_p \le s_x-s_z-s_{lca}\)。

左边是一个关于 \(p\) 的式子,右边是一个定值,也可以用类似的方法通过主席树求出。

那么允许离线的方法就很明显了,先建出树,然后对于每个点维护两棵主席树,分别表示第一种和第二种情况,然后查询的时候拆成两条路径分别查询即可(注意不要重复算 lca)。

现在考虑在线。一个经典的方法是启发式合并,由于答案和树的形态无关,可以每次把 size 小的连通块合并到 size 大的连通块上,对于 size 小的那个连通块,我们暴力重构需要维护的信息,包括倍增数组、前缀和数组和主席树。然后正常查询就好了。

启发式合并的复杂度是 \(O(n \log n)\),再加上重构倍增数组和主席树,复杂度就是 \(O(n \log n \log V)\)。

CODE

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

#define lch(p) tree[p].ch[0]
#define rch(p) tree[p].ch[1]

const int maxm=5e7+10,maxn=1e5+5;
const int lim=5e8;

struct Tree
{
    int ch[2],siz;
}S1[maxm],S2[maxm];
struct Edge
{
    int to,nxt;
}edge[maxn*2];

int n,S1tot,S2tot,tot,tp,q,la;
int val[maxn],head[maxn],fa[maxn],sz[maxn],rt1[maxn],rt2[maxn],f[maxn][25],sum[maxn],dep[maxn];

void add(int x,int y)
{
    tot++;
    edge[tot].to=y;
    edge[tot].nxt=head[x];
    head[x]=tot;
}

int findroot(int x){return fa[x]==x?x:fa[x]=findroot(fa[x]);}

void insert(Tree *tree,int &tot,int &p,int l,int r,int x)
{
    tree[++tot]=tree[p];
    p=tot;
    if(l==r){tree[p].siz++;return ;}
    int mid=l+r>>1;
    if(mid>=x) insert(tree,tot,lch(p),l,mid,x);
    else insert(tree,tot,rch(p),mid+1,r,x);
    tree[p].siz=tree[lch(p)].siz+tree[rch(p)].siz;
}
int query(Tree *tree,int p,int lp,int l,int r,int lx,int rx)
{
    if(lx<=l&&r<=rx) return tree[p].siz-tree[lp].siz;
    if(rx<l||r<lx) return 0;
    int mid=l+r>>1;
    return query(tree,lch(p),lch(lp),l,mid,lx,rx)+query(tree,rch(p),rch(lp),mid+1,r,lx,rx);
}

void dfs(int u,int fa,int d)
{
    dep[u]=d;
    f[u][0]=fa;
    for(int i=1;i<=20;i++) f[u][i]=f[f[u][i-1]][i-1];
    rt1[u]=rt1[fa],rt2[u]=rt2[fa];
    sum[u]=sum[fa]+val[u];
    insert(S1,S1tot,rt1[u],-lim,lim,sum[u]+val[u]);
    insert(S2,S2tot,rt2[u],-lim,lim,2*val[u]-sum[u]);
    for(int i=head[u];i;i=edge[i].nxt)
    {
        int v=edge[i].to;
        if(v==fa) continue;
        dfs(v,u,d+1);
    }
}

int Lca(int u,int v)
{
    if(dep[u]<dep[v]) swap(u,v);
    for(int i=20;i>=0;i--) if(dep[f[u][i]]>=dep[v]) u=f[u][i];
    if(u==v) return u;
    for(int i=20;i>=0;i--) if(f[u][i]!=f[v][i]) u=f[u][i],v=f[v][i];
    return f[u][0];
}

int main()
{
    scanf("%d",&tp);
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&val[i]);
        fa[i]=i,sz[i]=1,sum[i]=val[i],dep[i]=1;
        insert(S1,S1tot,rt1[i],-lim,lim,val[i]*2);
        insert(S2,S2tot,rt2[i],-lim,lim,val[i]);
    }

    while(q--)
    {
        int op,u,v;
        scanf("%d%d%d",&op,&u,&v);
        if(tp) u=u^la,v=v^la;
        if(!op)
        {
            int fu=findroot(u),fv=findroot(v);
            if(sz[fu]<sz[fv]) swap(u,v),swap(fu,fv);
            fa[fv]=fu,sz[fu]+=sz[fv];
            dfs(v,u,dep[u]+1);
            add(u,v);
            add(v,u);
        }
        else
        {
            int lca=Lca(u,v);
            int z=f[lca][0];
            la=query(S1,rt1[u],rt1[z],-lim,lim,-lim,sum[u])+query(S2,rt2[v],rt2[lca],-lim,lim,-lim,sum[u]-sum[lca]-sum[z]);
            printf("%d\n",la);
        }
    }
}

标签:26,int,tree,T3,tot,mid,tour,maxn,lca
From: https://www.cnblogs.com/binbinbjl/p/17818997.html

相关文章

  • 2609
    给你一个仅由 0 和 1 组成的二进制字符串 s 。  如果子字符串中 所有的 0 都在 1 之前 且其中 0 的数量等于 1 的数量,则认为 s 的这个子字符串是平衡子字符串。请注意,空子字符串也视作平衡子字符串。 返回  s 中最长的平衡子字符串长度。子字符串是字......
  • D - ABC Puzzle -- ATCODER ABC 326
    D-ABCPuzzlehttps://atcoder.jp/contests/abc326/tasks/abc326_dSampleInput1Copy5ABCBCACAABSampleOutput1CopyYesAC..B.BA.CC.BA.BA.C...CBA思路充分利用约束条件,构造算法,避免穷举所有情况,然后再根据约束条件判断情况的合法性。 如下代码,优......
  • 【U盘格式NTFS,FAT32,exFAT切换方法及各种文件系统区别】
    切换U盘格式步骤:1、格式化前,先确认把U盘离的数据进行备份,插入U盘,右击鼠标->点击格式化 2、进入格式化弹窗界面,选择所要修改的文件系统->点击开始->确定 各种文件系统区别:NTFS(NewTechnologyFileSystem意为新技术文件系统,其功能全面,应用最广泛。NTFS:1、NTFS这种格式的......
  • springboot3.1.5+文件上传+文件下载
    idea创建项目springbootdemo-download-upload加上thymeleaf模板maven依赖application.properties配置#thymeleaf页面缓存设置(默认为true)spring.thymeleaf.cache=false#单个上传文件大小限制(默认1MB)spring.servlet.multipart.max-file-size=10MB#总上传文件大小限制(默......
  • 2609. 最长平衡子字符串
    给你一个仅由 0 和 1 组成的二进制字符串 s 。  如果子字符串中 所有的 0 都在 1 之前 且其中 0 的数量等于 1 的数量,则认为 s 的这个子字符串是平衡子字符串。请注意,空子字符串也视作平衡子字符串。 返回  s 中最长的平衡子字符串长度。子字符串是字......
  • 实验三_OOP_张文瑞_202213260018
    任务1源代码:11#pragmaonce2233#include<iostream>44usingstd::cout;55usingstd::endl;6677classPoint{88public:99Point(intx0=0,inty0=0);1010~Point()=default;11111212intget_x()......
  • H.26x中SEI信息解读(转)
    原文:https://www.jianshu.com/p/23d9ab930b49作者:Li_Xianglin来源:简书H.264SEIhttp://www.itu.int/rec/T-REC-H.264 NALheader起始码(暗红底色)"0x00000001"分割出来的比特流即是NALunit,起始码紧跟的第一个字节(墨绿底色)是NALheader。上图“NALheader”一共出现了......
  • H265 NALU类型详细解析(转)
    原文:https://blog.csdn.net/u014470361/article/details/89541544作者:夜风~来源:CSDN前言在海思自hi3516a带的开发固件中,有H265编码的实例,在SAMPLE_VENC_1080P_CLASSIC(HI_VOID)应用实例中有涉及,那么本文将对H265的nal头和nalu的类型进行相关解析。h265Nalu类型解析 FF:......
  • [BZOJ2603] [POI2003] Motorways
    本题解思路类似kczno1在[POI2010]KOL-Railway的题解。如果\(l_i<l_j<r_i<r_j\)则连边\((i,j)\),题目转化为判断该图是否是二分图,如果是则给出染色方案。不妨先找出一个生成森林,然后染色并判断所有同颜色的点是否没有边相连。把所有\((l_i,r_i)\)按\(l\)从小......
  • NOIP 模拟13(NOIP A层联测26)
    100+100+20+17,T3按理说应该想到考虑两部分分别的贡献的,明明这个套路很常见。5k:就喜欢这种数据结构专场,多来点。A.origen先前缀和,以下\(p_i\)表示前缀异或和。考虑将一个数\(k\)二进制差分,假设拆成\(2^a+2^b+2^c\),则\(k^2=(2^a+2^b+2^c)\times(2^a+2^b+2^c)\),也就是指数......