CF600E
- 有一棵 $n$ 个结点的以 $1$ 号结点为根的有根树。
- 每个结点都有一个颜色，颜色是以编号表示的， $i$ 号结点的颜色编号为 $c_i$。
- 如果一种颜色在以 $x$ 为根的子树内出现次数最多，称其在以 $x$ 为根的子树中占主导地位。显然，同一子树中可能有多种颜色占主导地位。
- 你的任务是对于每一个 $i\in[1,n]$，求出以 $i$ 为根的子树中，占主导地位的颜色的编号和。
- $n\le 10^5,c_i\le n$
思路
对每个点建线段树，维护主导地位的颜色之和与主导地位颜色的出现次数。
然后直接线段树合并即可。
代码
#include<bits/stdc++.h>
#define ll long long
#define N 100010
#define Log 20
using namespace std;
int n,c[N];
int head[N],tot=0;
struct graph{
int v,next;
}edge[N<<1];
void add_edge(int u,int v) {edge[++tot].v=v,edge[tot].next=head[u],head[u]=tot;}
void add(int u,int v) {add_edge(u,v),add_edge(v,u);}
int root[N];
class SegmentTree{
private:
int lson[N*Log<<2],rson[N*Log<<2],maxn[N*Log<<2],total=0;
ll sum[N*Log<<2];
#define ls(p) lson[p]
#define rs(p) rson[p]
#define m(p) maxn[p]
#define s(p) sum[p]
#define mid (l+r>>1)
void update(int p) {
if(m(ls(p))==m(rs(p))) m(p)=m(ls(p)),s(p)=s(ls(p))+s(rs(p));
else if(m(ls(p))>m(rs(p))) m(p)=m(ls(p)),s(p)=s(ls(p));
else m(p)=m(rs(p)),s(p)=s(rs(p));
}
public:
void change(int &p,int l,int r,int x,int y) {
if(l>x||r<x) return ;
if(!p) p=++total;
if(l==r) {
m(p)+=y;
s(p)=l;
if(!m(p)) s(p)=0;
return ;
}
change(ls(p),l,mid,x,y),change(rs(p),mid+1,r,x,y);
update(p);
}
int merge(int p,int q,int l,int r) {
if(!p||!q) return p+q;
if(l==r) {
m(p)+=m(q);
s(p)=l;
if(!m(p)) s(p)=0;
return p;
}
ls(p)=merge(ls(p),ls(q),l,mid),rs(p)=merge(rs(p),rs(q),mid+1,r);
update(p);
return p;
}
ll ask(int p) {return s(p);}
}SMT;
void dfs_merge(int u,int fa) {
for(int i=head[u];i;i=edge[i].next) {
int v=edge[i].v;
if(v==fa) continue;
dfs_merge(v,u);
root[u]=SMT.merge(root[u],root[v],1,n);
}
}
void work() {
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&c[i]);
for(int i=1;i<=n;i++) SMT.change(root[i],1,n,c[i],1);
for(int i=1;i<n;i++) {
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
}
dfs_merge(1,1);
for(int i=1;i<=n;i++) printf("%lld ",SMT.ask(root[i]));
printf("\n");
}
int main() {
work();
return 0;
}洛谷P4556
首先村落里的一共有 $n$ 座房屋，并形成一个树状结构。然后救济粮分 $m$ 次发放，每次选择两个房屋 $(x, y)$，然后对于 $x$ 到 $y$ 的路径上（含 $x$ 和 $y$）每座房子里发放一袋 $z$ 类型的救济粮。
然后深绘里想知道，当所有的救济粮发放完毕后，每座房子里存放的最多的是哪种救济粮。
思路
对树上路径加，所以考虑树上差分。
问题在于差分完后如何求出答案。
考虑每个点建立一个线段树，然后直接自底向上线段树合并即可。
代码
#include<bits/stdc++.h>
#define N 100010
#define Log 20
using namespace std;
const int MAXN=100000;
int n,m;
int head[N],tot=0;
struct graph{
int v,next;
}edge[N<<1];
void add_edge(int u,int v) {edge[++tot].v=v,edge[tot].next=head[u],head[u]=tot;}
void add(int u,int v) {add_edge(u,v),add_edge(v,u);}
int depth[N],fa[N][Log],lg[N];
void dfs(int u) {
for(int i=1;i<=lg[depth[u]];i++) fa[u][i]=fa[fa[u][i-1]][i-1];
for(int i=head[u];i;i=edge[i].next) {
int v=edge[i].v;
if(v==fa[u][0]) continue;
fa[v][0]=u,depth[v]=depth[u]+1;
dfs(v);
}
}
int LCA(int x,int y) {
if(depth[x]<depth[y]) swap(x,y);
while(depth[x]>depth[y]) x=fa[x][lg[depth[x]-depth[y]]];
if(x==y) return x;
for(int i=lg[depth[x]];~i;i--) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
int root[N];
class SegmentTree{
private:
int lson[N*Log<<2],rson[N*Log<<2],cnt[N*Log<<2],id[N*Log<<2],total=0;
#define ls(p) lson[p]
#define rs(p) rson[p]
#define c(p) cnt[p]
#define i(p) id[p]
#define mid (l+r>>1)
void update(int p) {
if(c(ls(p))>=c(rs(p))) c(p)=c(ls(p)),i(p)=i(ls(p));
else c(p)=c(rs(p)),i(p)=i(rs(p));
}
public:
void change(int &p,int l,int r,int x,int y) {
if(l>x||r<x) return ;
if(!p) p=++total;;
if(l==r) {
c(p)+=y;
i(p)=l;
if(!c(p)) i(p)=0;
return ;
}
change(ls(p),l,mid,x,y),change(rs(p),mid+1,r,x,y);
update(p);
}
int merge(int p,int q,int l,int r) {
if(!p||!q) return p+q;
if(l==r) {
c(p)+=c(q);
i(p)=l;
if(!c(p)) i(p)=0;
return p;
}
ls(p)=merge(ls(p),ls(q),l,mid);
rs(p)=merge(rs(p),rs(q),mid+1,r);
update(p);
return p;
}
int ask(int p) {return i(p);}
}SMT;
int ans[N];
void merge(int u) {
for(int i=head[u];i;i=edge[i].next) {
int v=edge[i].v;
if(v==fa[u][0]) continue;
merge(v);
root[u]=SMT.merge(root[u],root[v],1,MAXN);
}
ans[u]=SMT.ask(root[u]);
}
void work() {
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++) {
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
}
lg[0]=-1;
for(int i=1;i<=n;i++) lg[i]=lg[i>>1]+1;
dfs(1);
for(int i=1;i<=m;i++) {
int x,y,z,lca;
scanf("%d%d%d",&x,&y,&z);
lca=LCA(x,y);
SMT.change(root[x],1,MAXN,z,1);
SMT.change(root[y],1,MAXN,z,1);
SMT.change(root[lca],1,MAXN,z,-1);
SMT.change(root[fa[lca][0]],1,MAXN,z,-1);
}
merge(1);
for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
}
int main() {
work();
return 0;
}洛谷P3224
永无乡包含 $n$ 座岛，编号从 $1$ 到 $n$ ，每座岛都有自己的独一无二的重要度，按照重要度可以将这 $n$ 座岛排名，名次用 $1$ 到 $n$ 来表示。某些岛之间由巨大的桥连接，通过桥可以从一个岛到达另一个岛。如果从岛 $a$ 出发经过若干座（含 $0$ 座）桥可以 到达岛 $b$ ，则称岛 $a$ 和岛 $b$ 是连通的。
现在有两种操作：
B x y 表示在岛 $x$ 与岛 $y$ 之间修建一座新桥。
Q x k 表示询问当前与岛 $x$ 连通的所有岛中第 $k$ 重要的是哪座岛，即所有与岛 $x$ 连通的岛中重要度排名第 $k$ 小的岛是哪座，请你输出那个岛的编号。
思路
连通，所以考虑用并查集来维护连通性。
另一个操作是查询某个连通块的第 $k$ 小。
所以考虑每个点建立一个权值线段树，对于每个 B 操作，在并查集合并的同时也进行线段树合并即可。
代码
#include<bits/stdc++.h>
#define N 100010
#define M 300010
#define Log 20
using namespace std;
int n,m,p[N],q,id[N];
int root[N];
class SegmentTree{
private:
int lson[M*Log<<2],rson[M*Log<<2],sum[M*Log<<2],total=0;
#define ls(p) lson[p]
#define rs(p) rson[p]
#define s(p) sum[p]
#define mid (l+r>>1)
void update(int p) {
s(p)=s(ls(p))+s(rs(p));
}
public:
void change(int &p,int l,int r,int x,int y) {
if(l>x||r<x) return ;
if(!p) p=++total;
if(l==r) {
s(p)+=y;
return ;
}
change(ls(p),l,mid,x,y),change(rs(p),mid+1,r,x,y);
update(p);
}
int merge(int p,int q,int l,int r) {
if(!p||!q) return p+q;
if(l==r) {
s(p)+=s(q);
return p;
}
ls(p)=merge(ls(p),ls(q),l,mid),rs(p)=merge(rs(p),rs(q),mid+1,r);
update(p);
return p;
}
int ask(int p,int l,int r,int x) {
if(l==r) return l;
if(x<=s(ls(p))) return ask(ls(p),l,mid,x);
return ask(rs(p),mid+1,r,x-s(ls(p)));
}
}SMT;
int pa[N];
int find(int x) {
if(x==pa[x]) return x;
return pa[x]=find(pa[x]);
}
void work() {
memset(id,-1,sizeof(id));
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&p[i]);
for(int i=1;i<=n;i++) pa[i]=i,SMT.change(root[i],1,n+1,p[i],1),id[p[i]]=i;
for(int i=1;i<=m;i++) {
int u,v;
scanf("%d%d",&u,&v);
int fu=find(u),fv=find(v);
pa[fv]=fu;
SMT.merge(root[fu],root[fv],1,n+1);
}
scanf("%d",&q);
for(int i=1;i<=q;i++) {
char op;
int x,y;
scanf(" %c%d%d",&op,&x,&y);
if(op=='Q') printf("%d\n",id[SMT.ask(root[find(x)],1,n+1,y)]);
else {
int fx=find(x),fy=find(y);
SMT.merge(root[fx],root[fy],1,n+1);
pa[fy]=fx;
}
}
}
int main() {
work();
return 0;
}CF490F
给出一棵带点权树，求树上最长上升子序列的长度
思路
本题数据很小，所以可以直接以每个点为起点 dfs 一遍求 LIS ，时间复杂度 $O(n^2 \log n)$ 。
如果 $n$ 大一些的话，这种做法就不行了。
考虑每个点建一个权值线段树，维护以 $i$ 为结尾的 LIS 和 LDS 长度。
在枚举一个点时，有两种 LIS ：
- 经过该点的 LIS 。
- 不经过该点的 LIS 。
第一种长度就是一个子树的 LIS 加另一个子树的 LDS 再加 1 。
另一种直接在线段树合并的过程中用左边的 LIS 与右边的 LDS 之和来更新 ans 即可。注意还可以反过来。
写起来细节很多，需要仔细想想。
调了好久 qaq 。
代码
直接 LIS
#include<bits/stdc++.h>
#define N 6010
using namespace std;
int n,r[N];
int head[N],tot=0;
struct graph{
int v,next;
}edge[N<<1];
void add_edge(int u,int v) {edge[++tot].v=v,edge[tot].next=head[u],head[u]=tot;}
void add(int u,int v) {add_edge(u,v),add_edge(v,u);}
int f[N],ans=0;
void dfs(int u,int fa) {
int pos=lower_bound(f+1,f+n+1,r[u])-f;
int tmp=f[pos];
f[pos]=r[u];
ans=max(ans,pos);
for(int i=head[u];i;i=edge[i].next) {
int v=edge[i].v;
if(v==fa) continue;
dfs(v,u);
}
f[pos]=tmp;
}
void work() {
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&r[i]);
for(int i=1;i<n;i++) {
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
}
memset(f,0x3f,sizeof(f));
for(int i=1;i<=n;i++) dfs(i,i);
printf("%d\n",ans);
}
int main() {
work();
return 0;
}线段树合并
#include<bits/stdc++.h>
#define N 6010
#define M 1000010
#define Log 20
using namespace std;
int n,r[N],t;
int head[N],tot=0;
struct graph{
int v,next;
}edge[N<<1];
void add_edge(int u,int v) {edge[++tot].v=v,edge[tot].next=head[u],head[u]=tot;}
void add(int u,int v) {add_edge(u,v),add_edge(v,u);}
vector<int> dscrt;
int val[M];
int ans=0;
int root[N];
class SegmentTree{
private:
int lson[N*Log<<2],rson[N*Log<<2],LIS[N*Log<<2],LDS[N*Log<<2],total=0;
#define ls(p) lson[p]
#define rs(p) rson[p]
#define I(p) LIS[p]
#define D(p) LDS[p]
#define mid (l+r>>1)
void update(int p) {
I(p)=max(I(ls(p)),I(rs(p)));
D(p)=max(D(ls(p)),D(rs(p)));
}
public:
void change(int &p,int l,int r,int x,int y,int z) {
if(l>x||r<x) return ;
if(!p) p=++total;
if(l==r) {
I(p)=max(I(p),y);
D(p)=max(D(p),z);
return ;
}
change(ls(p),l,mid,x,y,z),change(rs(p),mid+1,r,x,y,z);
update(p);
}
int merge(int p,int q,int l,int r) {
if(!p||!q) return p+q;
if(l==r) {
I(p)=max(I(p),I(q));
D(p)=max(D(p),D(q));
return p;
}
ans=max(ans,max(I(ls(p))+D(rs(q)),D(rs(p))+I(ls(q))));
ls(p)=merge(ls(p),ls(q),l,mid),rs(p)=merge(rs(p),rs(q),mid+1,r);
update(p);
return p;
}
int ask_lis(int p,int l,int r,int L,int R) {
if(l>R||r<L) return 0;
if(l>=L&&r<=R) return I(p);
return max(ask_lis(ls(p),l,mid,L,R),ask_lis(rs(p),mid+1,r,L,R));
}
int ask_lds(int p,int l,int r,int L,int R) {
if(l>R||r<L) return 0;
if(l>=L&&r<=R) return D(p);
return max(ask_lds(ls(p),l,mid,L,R),ask_lds(rs(p),mid+1,r,L,R));
}
}SMT;
void dfs(int u,int fa) {
int llis=0,llds=0;
for(int i=head[u];i;i=edge[i].next) {
int v=edge[i].v;
if(v==fa) continue;
dfs(v,u);
int lis=SMT.ask_lis(root[v],1,t,1,val[r[u]]-1),lds=SMT.ask_lds(root[v],1,t,val[r[u]]+1,t);
root[u]=SMT.merge(root[u],root[v],1,t);
ans=max(ans,max(llis+lds,llds+lis)+1);
llis=max(llis,lis),llds=max(llds,lds);
}
SMT.change(root[u],1,t,val[r[u]],llis+1,llds+1);
}
void work() {
scanf("%d",&n);
for(int i=1;i<=n;i++) {scanf("%d",&r[i]);dscrt.push_back(r[i]);}
sort(dscrt.begin(),dscrt.end());
t=unique(dscrt.begin(),dscrt.end())-dscrt.begin();
for(int i=0;i<t;i++) val[dscrt[i]]=i+1;
for(int i=1;i<n;i++) {
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
}
for(int i=1;i<=n;i++) SMT.change(root[i],1,t,val[r[i]],1,1);
dfs(1,1);
printf("%d\n",ans);
}
int main() {
work();
return 0;
}
