BZOJ-3307: 雨天的尾巴（轻重树链剖分+离散化+BST（
2018-10-03 本文已影响3人
AmadeusChan
题目：http://www.lydsy.com/JudgeOnline/problem.php?id=3307
024f78f0f736afc3873df27ab119ebc4b74512f8.jpg.png
0eb30f2442a7d9332781296caf4bd11373f00180.jpg.png
思路：
刚开始看这道题的时候拼命想在线做法，后来实在想不出来，就想离线的，很轻松就出解了：
首先，我们考虑对于一个序列而不是一棵树的情况，我们对于所有添加的区间[li,ri]，在li处做一个标记A，然后再在ri+1处做另一个标记B，然后从1开始扫描到n，对于当前位置，首先处理完所有该位置的标记，对于A，在数据结构了对添加的物品进行数量+1的操作，然后维护该数据结构，对于B，在数据结构了对添加的物品进行数量-1的操作，然后维护该数据结构，处理完标记之后，就利用该数据结构来查询当前最多的物品，即扫描到的位置最多的物品。
但是题目是一棵树，那么我们就想到了利用轻重树链剖分来将树划分成多条路径，然后连成一个序列，这时候，每个点(x,y)的路径就被拆成了多条路径，来对应序列上的区间（在同一重链上就是相同区间，否则再划出一个区间），根据轻重树链剖分的性质，划分的结果最多有m log n个区间，可以接受，然后维护物品数量的数据结构当然可以用BST来维护（我用的是离散化+线段树（按权值建树）），至于LCA，用Tarjan算法可以平摊O（1）解决。
复杂度：O(n log^2 n + m log^2 n)
速度还是给跪了，好慢：
dbb44aed2e738bd4a36c782ea38b87d6277ff964.jpg.png
代码（染色代码一长度娘又不让发了。。。）：
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define MAXN 100010
#define AddEdge(s,t) Add(s,t),Add(t,s)
#define MAXE 2000010
struct edge {
edge *next;
int t;
edge () {
next=NULL;
}
} *head[MAXN];
void Add(int s,int t) {
edge *p=new(edge);
p->t=t,p->next=head[s];
head[s]=p;
}
int n,m,size[MAXN],child[MAXN],parent[MAXN],h[MAXN];
int step[MAXN][3],lca[MAXN];
int ans[MAXN];
bool f[MAXN];
struct Node {
Node *next;
bool flag;
int z;
} *pre[MAXN];
void Maketree(int v) {
f[v]=false;
size[v]=1;
int S=0;
for (edge *p=head[v];p;p=p->next) if (f[p->t]) {
parent[p->t]=v;
h[p->t]=h[v]+1;
Maketree(p->t);
size[v]+=size[p->t];
if (size[p->t]>S) {
S=size[p->t],child[v]=p->t;
}
}
}
int first[MAXN],arr[MAXN],Index=0,Rank[MAXN];
void Makepath(int v,bool flag,int fir) {
f[v]=false;
arr[Rank[v]=++Index]=v;
if (flag) first[v]=v; else first[v]=fir;
if (child[v]) {
Makepath(child[v],false,first[v]);
for (edge *p=head[v];p;p=p->next) if (f[p->t]) {
Makepath(p->t,true,0);
}
}
}
struct node {
node *next;
int t,r;
node () {
next=NULL;
}
} *fro[MAXN];
int father[MAXN];
void Insert(int s,int t,int r) {
node *p=new(node);
p->t=t,p->next=fro[s],p->r=r;
fro[s]=p;
}
int Find(int v) {
int i,j=v;
for (i=v;father[i];i=father[i]) ;
while (father[j]) {
int k=father[j];
father[j]=i;
j=k;
}
return i;
}
void Tarjan(int v) {
f[v]=false;
for (node *p=fro[v];p;p=p->next) if (!f[p->t]) {
lca[p->r]=Find(p->t);
}
for (edge *p=head[v];p;p=p->next) if (f[p->t]) {
Tarjan(p->t);
father[Find(p->t)]=v;
}
}
void Insert_q(int s,int z,bool flag) {
Node *p=new(Node);
p->next=pre[s],p->z=z,p->flag=flag;
pre[s]=p;
}
int b[MAXN],c[MAXN],N=0;
bool Cmp(int x,int y) {
return x<y;
}
int Search(int k) {
int l=1,r=N;
if (c[l]==k) return l;
if (c[r]==k) return r;
while (l<=r) {
int mid=(l+r)>>1;
if (c[mid]==k) return mid;
if (c[mid]<k) l=mid; else r=mid;
}
}
struct Sgt {
int L[MAXN*4],R[MAXN*4],Max[MAXN*4],Size[MAXN*4];
Sgt () {
memset(L,0,sizeof(L));
memset(R,0,sizeof(R));
memset(Max,0,sizeof(Max));
memset(Size,0,sizeof(Size));
}
void Build(int l,int r,int t) {
L[t]=l,R[t]=r;
if (l==r) {
Max[t]=l;
return ;
}
Build(l,(l+r)>>1,t<<1),Build(((l+r)>>1)+1,r,(t<<1)^1);
}
void update(int t) {
if (L[t]<R[t]) {
if (Size[t<<1]>=Size[(t<<1)^1]) {
Size[t]=Size[t<<1],Max[t]=Max[t<<1];
} else Size[t]=Size[(t<<1)^1],Max[t]=Max[(t<<1)^1];
}
}
void Insert(int x,int y,int t) {
if (L[t]==R[t]) {
Size[t]+=y;
return ;
}
int mid=(L[t]+R[t])>>1;
if (x<=mid) Insert(x,y,t<<1); else Insert(x,y,(t<<1)^1);
update(t);
}
int Getmax() {
return Size[1]?Max[1]:0;
}
};
void getint(int &t) {
scanf("%d",&t);
}
void putint(int t) {
printf("%d\n",t);
}
int main() {
getint(n),getint(m);
memset(head,0,sizeof(head));
memset(fro,0,sizeof(fro));
for (int i=0;i++<n-1;) {
int s,t;
getint(s),getint(t);
AddEdge(s,t);
}
for (int i=0;i++<m;) {
getint(step[i][0]),getint(step[i][1]),getint(step[i][2]);
Insert(step[i][0],step[i][1],i),Insert(step[i][1],step[i][0],i);
}
memset(f,true,sizeof(f));
memset(child,0,sizeof(child));
parent[1]=h[1]=0;
h[0]=-1;
Maketree(1);
memset(f,true,sizeof(f));
Makepath(1,true,0);
memset(f,true,sizeof(f));
memset(father,0,sizeof(father));
Tarjan(1);
memset(pre,0,sizeof(pre));
for (int i=0;i++<m;) {
int l=step[i][0],he=h[lca[i]];
while (h[l]>=he) {
if (h[first[l]]>=he) {
Insert_q(Rank[first[l]],step[i][2],true);
Insert_q(Rank[l]+1,step[i][2],false);
l=parent[first[l]];
} else {
int r=Rank[l]-(h[l]-he);
Insert_q(r,step[i][2],true);
Insert_q(Rank[l]+1,step[i][2],false);
break;
}
}
l=step[i][1],he=h[lca[i]]+1;
while (h[l]>=he) {
if (h[first[l]]>=he) {
Insert_q(Rank[first[l]],step[i][2],true);
Insert_q(Rank[l]+1,step[i][2],false);
l=parent[first[l]];
} else {
int r=Rank[l]-(h[l]-he);
Insert_q(r,step[i][2],true);
Insert_q(Rank[l]+1,step[i][2],false);
break;
}
}
}
for (int i=0;i++<m;) b[i]=step[i][2];
sort(b+1,b+m+1,Cmp);
b[0]=0;
for (int i=0;i++<m;) if (b[i]!=b[i-1]) {
c[++N]=b[i];
}
Sgt T;
T.Build(1,N,1);
c[0]=0;
for (int i=0;i++<n;) {
for (Node *p=pre[i];p;p=p->next) if (p->flag) {
T.Insert(Search(p->z),1,1);
} else {
T.Insert(Search(p->z),-1,1);
}
ans[arr[i]]=T.Getmax();
}
for (int i=0;i++<n;) putint(c[ans[i]]);
return 0;
}
