【悬关】线段树合并写法样例能过但是 WA 0
查看原帖
【悬关】线段树合并写法样例能过但是 WA 0
743811
Shakespeare07楼主2023/9/21 19:16

rt.

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

#define pb push_back
#define rep(i, x, y) for (register int i = x; i <= y; ++ i )

inline int read() {
    int s = 0, w = 1; char c = getchar();
    while (! isdigit(c)){ if (c == '-') w = -1; c = getchar();}
    while (isdigit(c)){ s = (s << 3) + (s << 1) + (c ^ 48); c = getchar();}
    return s * w;
}
inline void write(register int x) {
    if (x < 0){
        putchar('-');
        x = -x;
    }
    if (x > 9) write(x / 10);
    putchar((char)(x % 10 + '0'));
}
inline void write_(register int x) {
    write(x);
    putchar(' ');
}
inline void writeline(register int x) {
    write(x);
    putchar('\n');
}

inline void chkmax(int &x, register int y) { if (y > x) x = y;}
inline void chkmin(int &x, register int y) { if (y < x) x = y;}

const int N=2e5+5;
const int M=N*70;

int n,a[N],fa[N],tot,b[N],cnt;
vector<int> g[N];

int rt[N],ans;
int s[M],add[M],tag[M],lc[M],rc[M];

void seg_add(int x,int v){
	s[x]+=v;
	if(tag[x]!=-1) tag[x]+=v;
	add[x]+=v;
}
void assign(int x,int v){
	chkmax(s[x],v);
	chkmax(tag[x],v);
}

void pushdown(int p){
	if(!lc[p]) lc[p]=++tot;
	if(!rc[p]) rc[p]=++tot;
	if(add[p]){
		s[lc[p]]+=add[p];
		s[rc[p]]+=add[p];
		add[lc[p]]+=add[p];
		add[rc[p]]+=add[p];
		tag[lc[p]]+=add[p];
		tag[rc[p]]+=add[p];
		add[p]=0;
		return;
	}
	if(tag[p]!=-1){
		chkmax(s[lc[p]],tag[p]);
		chkmax(s[rc[p]],tag[p]);
		chkmax(tag[lc[p]],tag[p]);
		chkmax(tag[rc[p]],tag[p]);
		tag[p]=-1;
		return;
	}
}

int merge(int x,int y,int l,int r){
	if(!x || !y) return x+y;
	if(!lc[x] && !rc[x]) swap(x,y);
	if(!lc[y] && !rc[y]){
		seg_add(x,s[y]);
		return x;
	}
	if(l==r){
		s[x]+=s[y];
		return x;
	}
	pushdown(x);
	pushdown(y);
	int mid=l+r>>1;
	lc[x]=merge(lc[x],lc[y],l,mid);
	rc[x]=merge(rc[x],rc[y],mid+1,r);
	return x;
}

int query(int p,int l,int r,int x){
	if(l==r) return s[p];
	pushdown(p);
	int mid=l+r>>1;
	if(x<=mid) return query(lc[p],l,mid,x);
	else return query(rc[p],mid+1,r,x);
}

int update(int p,int l,int r,int ql,int qr,int x){
	if(!p) p=++tot;
	if(l>=ql && r<=qr){
		assign(p,x);
		return p;
	}
	pushdown(p);
	int mid=l+r>>1;
	if(ql<=mid) lc[p]=update(lc[p],l,mid,ql,qr,x);
	if(qr>mid) rc[p]=update(rc[p],mid+1,r,ql,qr,x);
	return p;
}

void dfs(int x){
	int sum=0;
	for(int y:g[x]){
		if(y==fa[x]) continue;
		dfs(y);
		sum+=query(rt[y],1,n,a[x]);
		rt[x]=merge(rt[x],rt[y],1,n);
	}
	rt[x]=update(rt[x],1,n,1,a[x],sum+1);
}

signed main(){
	n=read();
	rep(i,1,n) a[i]=b[i]=read();
	sort(b+1,b+n+1);
	cnt=unique(b+1,b+n+1)-b-1;
	rep(i,1,n) a[i]=lower_bound(b+1,b+cnt+1,a[i])-b;
	rep(i,2,n){
		fa[i]=read();
		g[fa[i]].pb(i);
		g[i].pb(fa[i]);
	}
	
	memset(tag,-1,sizeof tag);
	dfs(1);
	writeline(query(rt[1],1,n,1));
	
	return 0;
}
/*
6
2 5 1 3 5 4
1
1
2
2
4
*/
2023/9/21 19:16
加载中...