BZOJ 4009 HNOI2015 接水果 树套树

题目大意:给定1棵树和m条路径,每条路径有1个权值,Q次询问,每次询问某条路经包括的所有路径中权值的第k小
原来精神污染那个题是这么做的啊QwQ
题解网上都有,我就直接贴代码了
没心情写题解了

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define M 40400
using namespace std;
struct Line{
int type;
int x,y1,y2,z;
Line() {}
Line(int _,int __,int ___,int ____,int _____):
type(_),x(__),y1(___),y2(____),z(_____) {}
bool operator < (const Line &l) const
{
if(x!=l.x)
return x < l.x;
return type > l.type;
}
}lines[M<<2];
struct Query{
int x,y,k,id;
bool operator < (const Query &q) const
{
return x < q.x ;
}
}queries[M];
struct abcd{
int to,next;
}table[M<<1];
int head[M],_tot;
int n,m,q,tot;
int dpt[M],fa[M][16],st[M],ed[M];
int ans[M];
void Add(int x,int y)
{
table[++_tot].to=y;
table[_tot].next=head[x];
head[x]=_tot;
}
void DFS(int x)
{
static int T;
int i;
dpt[x]=dpt[fa[x][0]]+1;
st[x]=++T;
for(i=head[x];i;i=table[i].next)
if(table[i].to!=fa[x][0])
{
fa[table[i].to][0]=x;
DFS(table[i].to);
}
ed[x]=T;
}
int LCA(int x,int y)
{
int j;
if(dpt[x]<dpt[y])
swap(x,y);
for(j=15;~j;j--)
if(dpt[fa[x][j]]>=dpt[y])
x=fa[x][j];
if(x==y) return x;
for(j=15;~j;j--)
if(fa[x][j]!=fa[y][j])
x=fa[x][j],y=fa[y][j];
return fa[x][0];
}
int Second_LCA(int x,int y)
{
int j;
for(j=15;~j;j--)
if(dpt[fa[y][j]]>dpt[x])
y=fa[y][j];
return y;
}
void Insert_Rectangle(int x1,int x2,int y1,int y2,int z)
{
lines[++tot]=Line(1,x1,y1,y2,z);
lines[++tot]=Line(-1,x2+1,y1,y2,z);
}
struct Segtree{
Segtree *ls,*rs;
int cnt;
void* operator new (size_t)
{
static Segtree *mempool,*C;
if(C==mempool)
mempool=(C=new Segtree[1<<16])+(1<<16);
C->ls=C->rs=0x0;
C->cnt=0;
return C++;
}
friend void Modify(Segtree *&p,int x,int y,int pos,int val)
{
int mid=x+y>>1;
if(!p) p=new Segtree;
p->cnt+=val;
if(x==y)
return ;
if(pos<=mid)
Modify(p->ls,x,mid,pos,val);
else
Modify(p->rs,mid+1,y,pos,val);
}
friend int Get_Kth(Segtree *stack[],int top,int x,int y,int k)
{
int i,mid=x+y>>1,cnt=0;
if(x==y) return mid;
for(i=1;i<=top;i++)
cnt+=stack[i]&&stack[i]->ls?stack[i]->ls->cnt:0;
if(k<=cnt)
{
for(i=1;i<=top;i++)
stack[i]=stack[i]?stack[i]->ls:0x0;
return Get_Kth(stack,top,x,mid,k);
}
else
{
for(i=1;i<=top;i++)
stack[i]=stack[i]?stack[i]->rs:0x0;
return Get_Kth(stack,top,mid+1,y,k-cnt);
}
}
};
namespace BIT{
Segtree *c[M];
void Update(int x,int pos,int val)
{
for(;x;x-=x&-x)
Modify(c[x],0,1000000000,pos,val);
}
int Get_Kth(int x,int k)
{
static Segtree *stack[M];int top;
top=0;
for(;x<=n;x+=x&-x)
stack[++top]=c[x];
return Get_Kth(stack,top,0,1000000000,k);
}
}
int main()
{
using namespace BIT;
int i,j,x,y,z;
cin>>n>>m>>q;
for(i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
Add(x,y);Add(y,x);
}
DFS(1);
for(j=1;j<=15;j++)
for(i=1;i<=n;i++)
fa[i][j]=fa[fa[i][j-1]][j-1];
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
if(st[x]>st[y])
swap(x,y);
int lca=LCA(x,y);
if(lca!=x)
Insert_Rectangle(st[x],ed[x],st[y],ed[y],z);
else
{
int temp=Second_LCA(x,y);
if(st[temp]!=1)
Insert_Rectangle(1,st[temp]-1,st[y],ed[y],z);
if(ed[temp]!=n)
Insert_Rectangle(st[y],ed[y],ed[temp]+1,n,z);
}
}
sort(lines+1,lines+tot+1);
for(i=1;i<=q;i++)
{
scanf("%d%d%d",&x,&y,&z);
if(st[x]>st[y])
swap(x,y);
queries[i].x=st[x];
queries[i].y=st[y];
queries[i].k=z;
queries[i].id=i;
}
sort(queries+1,queries+q+1);
for(j=1,i=1;i<=q;i++)
{

for(;j<=tot&&lines[j].x<=queries[i].x;j++)
Update(lines[j].y1-1,lines[j].z,-lines[j].type),
Update(lines[j].y2,lines[j].z,lines[j].type);

ans[queries[i].id]=Get_Kth(queries[i].y,queries[i].k);

}
for(i=1;i<=q;i++)
printf("%d
"
,ans[i]);
return 0;
}

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » BZOJ 4009 HNOI2015 接水果 树套树

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡