并不对劲的loj6498. 「雅礼集训 2018 Day2」农民

题目大意

有一棵\(n\)个点有点权\(w\)（可能有重复）的二叉树。\(m\)次操作，操作种类如下：
1.给出点\(x\)，修改\(x\)的权值；
2.给出点\(x\)，交换它和它的子树内所有点的左右儿子；
3.给出点\(x\)，问从根出发是否可以用“当前点点权小于\(w_x\)就往右走，大于\(w_x\)就往左走，等于\(w_x\)就停”来走到点\(x\)。
\(n,m\leq 10^5;\)

题解

当且仅当根到\(x\)路径上所有点满足“\(x\)在这个点左子树时点权大于\(w_x\)，在右子树时点权小于\(x\)”时操作3的答案是“是”。
相当于前一类点的最小值大于\(x\)，后一类点的最大值大于\(x\)。可以用两棵线段树维护。
操作2相当于两个线段树上的一些点。

代码
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define rep(i,x,y) for(register int i=(x);i<=(y);++i)
#define dwn(i,x,y) for(register int i=(x);i>=(y);--i)
#define view(u,k) for(int k=fir[u];~k;k=nxt[k])
#define maxn 100007
#define maxm 200007
#define ls ch[u][0]
#define rs ch[u][1]
#define mi ((l+r)>>1)
using namespace std;
int read()
{
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)&&ch!='-')ch=getchar();
	if(ch=='-')f=-1,ch=getchar();
	while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
	return x*f;
}
void write(int x)
{
	if(x==0){putchar('0'),putchar('\n');return;}
	int f=0;char ch[20];
	if(x<0)putchar('-'),x=-x;
	while(x)ch[++f]=x%10+'0',x/=10;
	while(f)putchar(ch[f--]);
	putchar('\n');
	return;
}
int n,m,a[maxn],son[maxn][2],wson[maxn],fa[maxn],siz[maxn],cntnd;
int dfn[maxn],tim,top[maxn],tr[maxn],dep[maxn],mn[maxn<<3],mx[maxn<<3],ch[maxn<<3][2],rtmx,rtmn;
int inf[2]={(int)(1e9+1),(int)(-1e9-1)};
int lt(int x){return x&(-x);}
void add(int x,int k){for(;x<=n;x+=lt(x))tr[x]^=k;return;}
int ask(int x){int k=0;for(;x;x-=lt(x))k^=tr[x];return k;}
void pu(int u)
{
	mx[u]=max(mx[ls],mx[rs]);
	mn[u]=min(mn[ls],mn[rs]);
	return;
}
int build(int l,int r)
{
	int u=++cntnd;
	if(l==r){mn[u]=inf[0],mx[u]=inf[1];return u;}
	ls=build(l,mi),rs=build(mi+1,r);pu(u);return u;
}
void adda(int u,int l,int r,int x,int k)
{
	if(l==r){mn[u]=mx[u]=k;return;}
	if(x<=mi)adda(ls,l,mi,x,k);
	else adda(rs,mi+1,r,x,k);
	pu(u);return;
}
void chg(int & ua,int & ub,int l,int r,int x,int y)
{
	if(x<=l&&r<=y){swap(ua,ub);return;}
	if(x<=mi)chg(ch[ua][0],ch[ub][0],l,mi,x,y);
	if(y>mi)chg(ch[ua][1],ch[ub][1],mi+1,r,x,y);
	pu(ua),pu(ub);return;
}
int aska(int u,int l,int r,int x,int y,int typ)//typ=0:mn
{
	if(x<=l&&r<=y){return typ?mx[u]:mn[u];}
	int res=inf[typ];
	if(x<=mi)res=aska(ls,l,mi,x,y,typ);
	if(y>mi)res=typ?max(res,aska(rs,mi+1,r,x,y,typ)):min(res,aska(rs,mi+1,r,x,y,typ));
	return res;
}
void getson(int u)
{
	siz[u]=1;
	rep(i,0,1)if(son[u][i])
	{
		dep[son[u][i]]=dep[u]+1,fa[son[u][i]]=u,getson(son[u][i]),siz[u]+=siz[son[u][i]];
		if(!wson[u]||siz[wson[u]]a[x])puts("YES");
			else puts("NO");
		}
	}
	return 0;
}
一些感想

为啥我打不过人？？？

树链剖分线段树+题目来源：loj

相关

#直径，线段树#51nod 1766 树上的最远点对

「NOI2020」命运（树形DP+线段树合并）

线段树学习笔记 1

关于 线段树 的一些认识

线段树

[NOI2015]软件包管理器（巧用线段树）

P6242 【模板】线段树 3

P5494 【模板】线段树分裂

CF1557D Ezzat and Grid（线段树）

cf739 C. Alyona and towers（线段树）

可持久化线段树

Codeforces Round #625 Div1 C,二维偏序，排序+线段树

标签