首页 > 其他分享 >SP30785 ADAAPPLE - Ada and Apple 题解

SP30785 ADAAPPLE - Ada and Apple 题解

时间:2024-11-02 08:49:22浏览次数:1  
标签:siz ADAAPPLE Apple rs int 题解 mid tag hs

洛谷题目传送门

博客园可能食用更佳

题目大意:

给定一棵权值为 \(0\) 或 \(1\) 的树,\(n\) 个点,\(q\) 次操作:

  • 0 i 把结点 \(i\) 的权值取反;

  • 1 i j 询问点 \(i\) 到点 \(j\) 的最短路径上权值是否全为 \(0\) 或全为 \(1\)。

题目分析:

树上操作,看了下操作发现是树剖板子题。

开一棵线段树,操作一单点取反,考虑维护懒标记 \(tag\) 记录结点的取反状态即可,操作二求一下路径上权值总和,再与最短路径长度比较一下即可。

时间复杂度:\(\mathcal O(q \log n)\)。

Code:

#include<bits/stdc++.h>
#define ls u<<1
#define rs u<<1|1
#define il inline
#define pb push_back
using namespace std;
il int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48),ch=getchar();}return x*f;}
il char getc(){char ch=getchar();while(ch=='\n'||ch=='\r'||ch==' ')ch=getchar();return ch;}
const int N=3e5+5;
int n,q,a[N];
vector<int> g[N];
int fa[N],dep[N],siz[N],hs[N];
void dfs1(int u,int fath)
{
	fa[u]=fath,dep[u]=dep[fath]+1;
	siz[u]=1,hs[u]=-1;
	for(auto v:g[u])
	{
		if(v==fath) continue;
		dfs1(v,u),siz[u]+=siz[v];
		if(hs[u]==-1||siz[v]>siz[hs[u]]) hs[u]=v;
	}
}
int cnt,top[N],w[N],pos[N];
void dfs2(int u,int t)
{
	top[u]=t,pos[w[u]=++cnt]=u;
	if(~hs[u]) dfs2(hs[u],t);
	for(auto v:g[u])
		if(v^hs[u]&&fa[u]^v) dfs2(v,v);
}
int t[N<<2],tag[N<<2];
void push_up(int u) {t[u]=t[ls]+t[rs];}
void build(int u,int l,int r)
{
	if(l==r) return t[u]=a[pos[l]],void();
	int mid=(l+r)>>1;
	build(ls,l,mid),build(rs,mid+1,r);
	push_up(u);
}
void push_down(int u,int l,int r)
{
	if(!tag[u]) return;
	tag[ls]^=1,tag[rs]^=1;
	int mid=(l+r)>>1;
	t[ls]=mid-l+1-t[ls],t[rs]=r-mid-t[rs];
	tag[u]=0;
}
void update(int u,int l,int r,int x,int y)
{
	if(y<l||r<x) return;
	if(x<=l&&r<=y) return tag[u]^=1,t[u]=r-l+1-t[u],void();
	push_down(u,l,r);
	int mid=(l+r)>>1;
	if(x<=mid) update(ls,l,mid,x,y);
	if(y>mid) update(rs,mid+1,r,x,y);
	push_up(u);
}
int query(int u,int l,int r,int x,int y)
{
	if(y<l||r<x) return 0;
	if(x<=l&&r<=y) return t[u];
	push_down(u,l,r);
	int mid=(l+r)>>1,res=0;
	if(x<=mid) res+=query(ls,l,mid,x,y);
	if(y>mid) res+=query(rs,mid+1,r,x,y);
	return res;
}
bool range_query(int u,int v)
{
	int ans=0,sum=0;
	while(top[u]^top[v])
	{
		if(dep[top[u]]<dep[top[v]]) swap(u,v);
		ans+=query(1,1,n,w[top[u]],w[u]);
		sum+=w[u]-w[top[u]]+1;
		u=fa[top[u]];
	}
	if(dep[u]<dep[v]) swap(u,v);
	ans+=query(1,1,n,w[v],w[u]);
	sum+=w[u]-w[v]+1;
	return !ans||ans==sum;
}
int main()
{
	n=read(),q=read();
	for(int i=1;i<=n;i++) a[i]=getc()^48;
	for(int i=1;i<n;i++)
	{
		int u=read()+1,v=read()+1;
		g[u].pb(v),g[v].pb(u);
	}
	dfs1(1,0),dfs2(1,1),build(1,1,n);
	while(q--)
	{
		int opt=read(),x=read()+1,y;
		if(opt&1) y=read()+1,puts(range_query(x,y)?"YES":"NO");
		else update(1,1,n,w[x],w[x]);
	}
	return 0;
}

标签:siz,ADAAPPLE,Apple,rs,int,题解,mid,tag,hs
From: https://www.cnblogs.com/lunjiahao/p/18521575

相关文章

  • Apple Safari 18 - macOS 专属浏览器 (独立安装包下载)
    AppleSafari18-macOS专属浏览器(独立安装包下载)适用于macOSSonoma和macOSVentura的Safari浏览器18请访问原文链接:https://sysin.org/blog/apple-safari-18/查看最新版。原创作品,转载请保留出处。作者主页:sysin.org之前Safari浏览器伴随macOS更新一起发......
  • P5298 Minimax 题解
    传送门小\(C\)有一棵\(n\)个结点的有根树,根是\(1\)号结点,且每个结点最多有两个子结点。定义结点\(x\)的权值为:1.若\(x\)没有子结点,那么它的权值会在输入里给出,保证这类点中每个结点的权值互不相同。2.若\(x\)有子结点,那么它的权值有\(p_x\)的概率是它的子结点......
  • AT_utpc2012_07 k番目の文字列 题解
    模拟赛搬了这个题,来写个题解。\(n\)这么小,不是状压就是很多很多维DP(暴论)。状压我没想出来,那就正常DP。考虑依次填入字符串的每个位置,记\(f(i,j,num,op)\)表示填了前\(i\)个位置,其中比\(s_0\)小的有\(j\)个,目前字典序比\(s\)小的子串有\(num\)个的方案数,\(op\)表......
  • 天津大学2024华为杯I.个大的大个 题解
    原题链接https://acm.tju.edu.cn/problem/P2040学校oj好像挂了,题解发不出去,又没有草稿功能,所以先存在这里了。前言华为杯时候对字符串不太熟,加上看错题了导致没做出这题,很可惜,苦练几个月,现在已经成为串串大师,回过头来秒一下这题发个题解泄恨。题意给定一个长为\(n\)的字符......
  • 2024御网线上Pwn方向题解
    ASMChecksec检查保护基本上保护都关闭了64位ida逆向程序只有一段,并且返回地址就是输入的数据,看起来就是srop了,找一下可以用的gadget通过异或清空rax值,然后通过异或ecx和1,异或rax和rcx即可增加rax的值,同理左移一位同样可以增加rax的值,将rax增加到0xf然后打srop,程序还给出了......
  • CodeForces Dora and C++ (2007C) 题解
    CodeForcesDoraandC++(2007C)题解题意给一个数组\(c_{1...n}\),定义数组的\(range\)是最大值减最小值,即极差。给出两个值\(a\)和\(b\),每步操作中,可给数组中任一一个数增大\(a\)或增大\(b\)。问任意步操作后(可以是\(0\)步),极差的最小值。思路(要直接看答案可以跳......
  • 第八届御网杯线下赛Pwn方向题解
    由于最近比赛有点多,而且赶上招新,导致原本应该及时总结的比赛搁置了,总结来说还是得多练,因为时间很短像这种线下赛,一般只有几个小时,所以思路一定要清晰,我还是经验太少了,导致比赛力不从心,先鸽了~Skillchecksec检查保护(没有开PIE和Canary)ida逆向分析一下不同的选项对应不同的功......
  • 【考试题解】多校A层冲刺NOIP2024模拟赛17
    A.网格(grid)题目内容给你一个\(n\timesm\)的字符网格\(s\),\(s_{i,j}\in[1,9]\cup\{+,*\}\),从\((1,1)\)开始,仅向下或向右走并最终到达\((n,m)\)的路径被称为合法路径,求所有合法路径对应的表达式的运算结果之和,答案对\(998244353\)取模。部分分44pts爆搜,枚举路径,......
  • 2024 -- 国庆集训 -- 临沂四中 -- 10月01 日 -- S/N模拟赛#1 题解
    A.2025--[炼石计划--NOIP模拟三]--T1--矩形赛时草了个\(O(n^4\log(n))\)竟然能过70分虽然本来就是这么分配的,发现正解只需将二分改为双指针就可以了,最气的是上面计算的时候用到还是尺取下面就用的二分(唐诗)。其实这题就是暴力,然后在低级的暴力上加一些操作变得稍微高级一......
  • abc318_g Typical Path Problem 题解 圆方树
    题目链接:https://atcoder.jp/contests/abc318/tasks/abc318_g题目大意:给出一个有\(n\)个顶点和\(m\)条边的无向连通图\(G\),没有重边和自环。顶点的编号为\(1\simn\),边的编号为\(1\simm\),第\(i\)条边连接顶点\(u_i\)和\(v_i\)。给出图上三个不同的顶点\(A,B,C......