树(tree)
题目描述
n ≤ 1 0 5 n\leq 10^5
n
≤
1
0
5
解法
以前是暴力水过去的，结果今天考到了加强版，然后就凉了
不难发现可以用线段树分别维护以
u u
u
为根的最长上升子序列和最长下降子序列，然后拼起来就可以了。
线段树的下标是开始位置的权值，可以快速算出
a [ u ] a[u]
a
[
u
]
为起始点的最长上升子序列和最长下降子序列。然后还要把子树的线段树合并上来，合并的时候可以更新一下答案（左右子树的子序列拼起来）
在
d f s dfs
d
f
s
的时候顺便算一下经过
a [ u ] a[u]
a
[
u
]
的子序列即可，时间复杂度
O ( n log n ) O(n\log n)
O
(
n
lo
g
n
)
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
const int M = 100005;
const int up = 100000;
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,m,tot,cnt,ans,a[M],b[M],f[M],rt[M];
int mx[50*M][2],ls[50*M],rs[50*M];
struct edge
{
int v,next;
edge(int V=0,int N=0) : v(V) , next(N) {}
}e[2*M];
void ins(int &x,int l,int r,int id,int f,int t)
{
if(!x) x=++cnt;
mx[x][f]=max(mx[x][f],t);
if(l==r) return ;
int mid=(l+r)>>1;
if(mid>=id) ins(ls[x],l,mid,id,f,t);
else ins(rs[x],mid+1,r,id,f,t);
}
int ask(int x,int l,int r,int L,int R,int f)
{
if(L>r || l>R || !x) return 0;
if(L<=l && r<=R) return mx[x][f];
int mid=(l+r)>>1;
return max(ask(ls[x],l,mid,L,R,f),ask(rs[x],mid+1,r,L,R,f));
}
int merge(int x,int y)
{
if(!x || !y) return x+y;
ans=max(ans,max(mx[ls[x]][0]+mx[rs[y]][1],mx[rs[x]][1]+mx[ls[y]][0]));
mx[x][0]=max(mx[x][0],mx[y][0]);
mx[x][1]=max(mx[x][1],mx[y][1]);
ls[x]=merge(ls[x],ls[y]);
rs[x]=merge(rs[x],rs[y]);
return x;
}
void dfs(int u,int fa)
{
int lis=0,lds=0;
for(int i=f[u];i;i=e[i].next)
{
int v=e[i].v;
if(v==fa) continue;
dfs(v,u);
int t1=ask(rt[v],1,m,1,a[u]-1,0);
int t2=ask(rt[v],1,m,a[u]+1,up,1);
ans=max(ans,max(t1+lds,t2+lis)+1);
lis=max(lis,t1);
lds=max(lds,t2);
rt[u]=merge(rt[u],rt[v]);
}
ins(rt[u],1,m,a[u],0,lis+1);
ins(rt[u],1,m,a[u],1,lds+1);
}
int main()
{
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
n=read();
for(int i=1;i<=n;i++)
a[i]=b[i]=read();
sort(b+1,b+1+n);
m=unique(b+1,b+1+n)-b-1;
for(int i=1;i<=n;i++)
a[i]=lower_bound(b+1,b+m+1,a[i])-b;
for(int i=1;i<n;i++)
{
int u=read(),v=read();
e[++tot]=edge(v,f[u]),f[u]=tot;
e[++tot]=edge(u,f[v]),f[v]=tot;
}
dfs(1,0);
printf("%d\n",ans);
}
多项式(poly)
题目描述
给定多项式
f 1 ( x ) = ∑ i = 0 n a i ⋅ x i f_1(x)=\sum_{i=0}^na_i\cdot x^i
f
1
(
x
)
=
∑
i
=
0
n
a
i
⋅
x
i
，有关于
f f
f
的递推式
f i ( x ) = b i f i − 1 ′ ( x ) + c i f i − 1 ( x ) f_i(x)=b_if_{i-1}'(x)+c_if_{i-1}(x)
f
i
(
x
)
=
b
i
f
i
−
1
′
(
x
)
+
c
i
f