A1219. 채광(진허민) 나무 사슬 분해 + 라인 트리 + DP
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define X 65536
#define Y 2147483647
#define N 20005
#define M 55
using namespace std;
int n,m,A,B,C,Q;
int cnt,dfn;
int head[N],next[N],list[N];
int a[N][M];
int l[N<<2],r[N<<2],mx1[N<<2][M],mx2[N<<2][M];
int ans1[M],ans2[M];
int size[N],fa[N],in[N],out[N],pos[N],belong[N];
inline int read()
{
int a=0,f=1; char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1; c=getchar();}
while (c>='0'&&c<='9') {a=a*10+c-'0'; c=getchar();}
return a*f;
}
inline void insert(int x,int y)
{
next[++cnt]=head[x];
head[x]=cnt;
list[cnt]=y;
}
inline int get_int()
{
A=((A^B)+(B/X)+(B*X))&Y;
B=((A^B)+(A/X)+(A*X))&Y;
return (A^B)%Q;
}
void dfs1(int x)
{
size[x]=1;
for (int i=head[x];i;i=next[i])
{
fa[list[i]]=x;
dfs1(list[i]);
size[x]+=size[list[i]];
}
}
void dfs2(int x,int chain)
{
in[x]=++dfn; pos[dfn]=x; belong[x]=chain;
int k=0;
for (int i=head[x];i;i=next[i])
if (size[list[i]]>size[k]) k=list[i];
if (!k) {out[x]=in[x]; return;}
dfs2(k,chain);
for (int i=head[x];i;i=next[i])
if (list[i]!=k) dfs2(list[i],list[i]);
out[x]=dfn;
}
inline void pushup(int k)
{
memset(mx1[k],0,sizeof(mx1[k]));
for (int i=0;i<=m;i++)
for (int j=0;j<=m-i;j++)
mx1[k][i+j]=max(mx1[k][i+j],mx1[k<<1][i]+mx1[k<<1|1][j]);
for (int i=1;i<=m;i++) mx2[k][i]=max(mx2[k<<1][i],mx2[k<<1|1][i]);
}
void build(int k,int x,int y)
{
l[k]=x; r[k]=y;
if (l[k]==r[k])
{
for (int i=1;i<=m;i++) mx1[k][i]=mx2[k][i]=a[pos[l[k]]][i];
return;
}
int mid=l[k]+r[k]>>1;
build(k<<1,x,mid); build(k<<1|1,mid+1,y);
pushup(k);
}
void query1(int k,int x,int y)
{
if (l[k]>=x&&r[k]<=y)
{
for (int i=m;i;i--)
for (int j=i;j;j--)
ans1[i]=max(ans1[i],ans1[i-j]+mx1[k][j]);
return;
}
int mid=l[k]+r[k]>>1;
if (y<=mid) query1(k<<1,x,y);
else if (x>mid) query1(k<<1|1,x,y);
else query1(k<<1,x,mid),query1(k<<1|1,mid+1,y);
}
void query2(int k,int x,int y)
{
if (l[k]>=x&&r[k]<=y)
{
for (int i=1;i<=m;i++) ans2[i]=max(ans2[i],mx2[k][i]);
return;
}
int mid=l[k]+r[k]>>1;
if (y<=mid) query2(k<<1,x,y);
else if (x>mid) query2(k<<1|1,x,y);
else query2(k<<1,x,mid),query2(k<<1|1,mid+1,y);
}
inline void ask(int f,int x)
{
x=fa[x];
while (belong[x]!=belong[f])
{
query2(1,in[belong[x]],in[x]);
x=fa[belong[x]];
}
query2(1,in[f],in[x]);
}
void change(int k,int x)
{
if (l[k]==r[k])
{
for (int i=1;i<=m;i++) mx1[k][i]=mx2[k][i]=a[pos[l[k]]][i];
return;
}
int mid=l[k]+r[k]>>1;
if (x<=mid) change(k<<1,x); else change(k<<1|1,x);
pushup(k);
}
int main()
{
n=read(); m=read(); A=read(); B=read(); Q=read();
for (int i=2;i<=n;i++)
{
int x=read();
insert(x,i);
}
for (int i=1;i<=n;i++)
{
for (int j=1;j<=m;j++) a[i][j]=get_int();
sort(a[i]+1,a[i]+m+1);
}
dfs1(1); dfs2(1,1); build(1,1,n);
C=read();
while (C--)
{
int opt=read();
if (opt)
{
int u=read(),v=read(),ans=0;
memset(ans1,0,sizeof(ans1));
memset(ans2,0,sizeof(ans2));
query1(1,in[u],out[u]);
if (u!=v) ask(v,u);
for (int i=0;i<=m;i++) ans=max(ans,ans1[i]+ans2[m-i]);
printf("%d
",ans);
}
else
{
int p=read();
for (int j=1;j<=m;j++) a[p][j]=get_int();
sort(a[p]+1,a[p]+m+1);
change(1,in[p]);
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.