[HNOI2015]接水果

C++14(g++5.4) 解法, 执行用时: 140ms, 内存消耗: 8680K, 提交时间: 2019-10-29 22:14:00

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10;

//结构体和重载
struct Matrix { int x1,y1,x2,y2,k; } t[N];
struct Fruit { int x,y,k,id; } q[N],lq[N],rq[N];
struct Line { int y1,y2,x,v; } p[N];
bool operator <(Matrix a,Matrix b) { return a.k<b.k; }
bool operator <(Fruit a,Fruit b) { return a.x<b.x; }
bool operator <(Line a,Line b) { return a.x<b.x; }

//邻接表
struct Edge { int v,nxt; } e[N];
int head[N],cnt=0;

inline void addEdge(int u,int v) {
    e[++cnt]=(Edge){v,head[u]},head[u]=cnt;
}

//变量
int n,P,Q;
int f[18][N],dep[N];
int st[N],ed[N],dfs_clock=0,tot=0;
int ans[N];

//树状数组
int c[N];
#define lowbit(x) (x&-x)
inline void add(int x,int y) {
    for (;x<=n;x+=lowbit(x)) c[x]+=y;
}
inline int sum(int x) {
    int ans=0;
    for (;x;x-=lowbit(x)) ans+=c[x];
    return ans;
}

//函数
inline void dfs(int u,int fa) {
    f[0][u]=fa,dep[u]=dep[fa]+1,st[u]=++dfs_clock;
    for (re int i=1;i<=15;++i) f[i][u]=f[i-1][f[i-1][u]];
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (v==fa) continue;
        dfs(v,u);
    }
    ed[u]=dfs_clock;
}

inline int LCA(int u,int v,int op) {
    if (dep[u]<dep[v]) swap(u,v);
    for (re int i=15;i>=0;--i)
        if (dep[f[i][u]]>dep[v]) u=f[i][u];
    if (f[0][u]==v) return op?u:v;
    u=f[0][u];
    for (re int i=15;i>=0;--i)
        if (f[i][u]!=f[i][v]) u=f[i][u],v=f[i][v];
    return op?u:f[0][u];
}

inline void solve(int L,int R,int lval,int rval) {
    if (L>R) return;
    if (lval==rval) {
        for (re int i=L;i<=R;++i) ans[q[i].id]=lval;
        return;
    }
    int mid=(lval+rval)>>1,lt=0,rt=0,cnt=0;
    for (re int i=lval;i<=mid;++i) {
        p[++cnt]=(Line){t[i].y1,t[i].y2,t[i].x1,1};
        p[++cnt]=(Line){t[i].y1,t[i].y2,t[i].x2+1,-1};
    }
    sort(p+1,p+cnt+1);
    int pos=1;
    for (re int i=L;i<=R;++i) {
        while (pos<=cnt&&p[pos].x<=q[i].x)
            add(p[pos].y1,p[pos].v),add(p[pos].y2+1,-p[pos].v),++pos;
        int s=sum(q[i].y);
        if (q[i].k<=s) lq[++lt]=q[i];
        else q[i].k-=s,rq[++rt]=q[i];
    }
    for (re int i=1;i<pos;++i)
        add(p[i].y1,-p[i].v),add(p[i].y2+1,p[i].v);
    for (re int i=1;i<=lt;++i) q[L+i-1]=lq[i];
    for (re int i=1;i<=rt;++i) q[L+lt+i-1]=rq[i];
    solve(L,L+lt-1,lval,mid),solve(L+lt,R,mid+1,rval);
}

int main() {
    n=read(),P=read(),Q=read();
    for (re int i=1;i<n;++i) {
        int u=read(),v=read();
        addEdge(u,v),addEdge(v,u);
    }
    dfs(1,0);
    for (re int i=1;i<=P;++i) {
        int u=read(),v=read(),k=read();
        if (st[u]>st[v]) swap(u,v);
        int lca=LCA(u,v,0);
        if (u!=lca) t[++tot]=(Matrix){st[u],st[v],ed[u],ed[v],k};
        else {
            int d=LCA(u,v,1);
            if (st[d]!=1) t[++tot]=(Matrix){1,st[v],st[d]-1,ed[v],k};
            if (ed[d]!=n) t[++tot]=(Matrix){st[v],ed[d]+1,ed[v],n,k};
        }
    }
    for (re int i=1;i<=Q;++i) {
        int u=read(),v=read(),k=read();
        if (st[u]>st[v]) swap(u,v);
        q[i]=(Fruit){st[u],st[v],k,i};
    }
    sort(t+1,t+tot+1); sort(q+1,q+Q+1);
    solve(1,Q,1,tot);
    for (re int i=1;i<=Q;++i) printf("%d\n",t[ans[i]].k);
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 142ms, 内存消耗: 20464K, 提交时间: 2019-03-16 10:37:48

#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<vector>
#define MAXN 200005
#define MAXM 400005
using namespace std;

char buf[1<<20],*p1,*p2;
#define GC (p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?0:*p1++)
inline int _R(){
	char s=GC;int sign=0,v=0;
	while((s!='-')&&(s>57||s<48))s=GC;
	if(s=='-')s=GC,sign=1;
	for(;s>47&&s<58;s=GC)v=v*10+s-48;
	return sign?-v:v;
}

int N,P,Q,Ans[MAXN];

struct rec{
	int l,r,d,u,v;
	rec(int ll=0,int rr=0,int dd=0,int uu=0,int vv=0){
		l=ll;r=rr;u=uu;d=dd;v=vv;
		if(l>d)swap(l,d),swap(r,u);
		else if(l==d&&r>u)swap(r,u);
	}
}A[MAXN*2];int cnt;

struct node{
	int u,v,k,id;
};

struct line{
	int l,d,u,k,id;
}L[MAXN];
bool operator<(line a,line b){
	return a.l==b.l?a.id<b.id:a.l<b.l;
}

bool cmpv(rec a,rec b){
	return a.v<b.v;
}

bool cmpp(rec a,rec b){
	return a.l==b.l?a.r<b.r:a.l<b.l;
}

int en[MAXM],nex[MAXM],las[MAXN],tot;
void Add(int x,int y){
	en[++tot]=y;
	nex[tot]=las[x];
	las[x]=tot;
}

int fa[MAXN][17],dep[MAXN],In[MAXN],Out[MAXN],VT;
void DFS(int x,int f){
	int i,y;
	In[x]=++VT;
	dep[x]=dep[f]+1;fa[x][0]=f;
	for(i=1;i<17;i++)fa[x][i]=fa[fa[x][i-1]][i-1];
	for(i=las[x];i;i=nex[i]){
		y=en[i];if(y==f)continue;
		DFS(y,x);
	}
	Out[x]=VT;
}

int LCA(int x,int y){
	if(dep[x]<dep[y])swap(x,y);
	int d=dep[x]-dep[y],i;
	for(i=0;i<17;i++)if(d>>i&1)x=fa[x][i];
	if(x==y)return x;
	for(i=16;i>=0;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
	return fa[x][0];
}

int gf(int x,int d){
	for(int i=0;i<17;i++)if(d>>i&1)x=fa[x][i];
	return x;
}

int C[MAXN];
void Modify(int x,int k){
	for(int i=x;i<=N;i+=(i&-i))C[i]+=k;
}
int GetSum(int x){
	int i,ret=0;
	for(i=x;i;i^=(i&-i))ret+=C[i];
	return ret;
}

vector<node>qry;

void Solve(int l,int r,vector<node>T){
	if(l==r){
		for(int i=0;i<T.size();i++)Ans[T[i].id]=A[l].v;
		return;
	}
	int i,mid=l+r>>1,cnt=0,t;
	vector<node>Q1,Q2;
	for(i=l;i<=mid;i++){
		L[++cnt]=(line){A[i].l,A[i].d,A[i].u,1,0};
		L[++cnt]=(line){A[i].r,A[i].d,A[i].u,-1,N+P+Q};
	}
	for(i=0;i<T.size();i++)L[++cnt]=(line){T[i].u,T[i].v,0,T[i].k,T[i].id};
	sort(L+1,L+cnt+1);
	for(i=1;i<=cnt;i++){
		if(L[i].id>=1&&L[i].id<=Q){
			t=GetSum(L[i].d);
			if(t>=L[i].k)Q1.push_back((node){L[i].l,L[i].d,L[i].k,L[i].id});
			else Q2.push_back((node){L[i].l,L[i].d,L[i].k-t,L[i].id});
		}
		else{
			Modify(L[i].d,L[i].k);
			Modify(L[i].u+1,-L[i].k);
		}
	}
	Solve(l,mid,Q1);
	Solve(mid+1,r,Q2);
}

int main(){
	int i,x,y,a,b,c,d,lca;
	N=_R();P=_R();Q=_R();
	for(i=1;i<N;i++){
		x=_R();y=_R();
		Add(x,y);Add(y,x);
	}
	DFS(1,0);
	for(i=1;i<=P;i++){
		a=_R();b=_R();c=_R();
		lca=LCA(a,b);
		if(lca==a||lca==b){
			if(dep[a]<dep[b])swap(a,b);
			d=gf(a,dep[a]-dep[b]-1);
			A[++cnt]=rec(In[a],Out[a],1,In[d]-1,c);
			if(Out[d]+1<=N)A[++cnt]=rec(In[a],Out[a],Out[d]+1,N,c);
		}
		else A[++cnt]=rec(In[a],Out[a],In[b],Out[b],c);
	}
	sort(A+1,A+cnt+1,cmpv);
	for(i=1;i<=Q;i++){
		x=_R();y=_R();a=_R();
		if(In[x]>In[y])swap(x,y);
		qry.push_back((node){In[x],In[y],a,i});
	}
	Solve(1,cnt,qry);
	for(i=1;i<=Q;i++)printf("%d\n",Ans[i]);
}

详情