P11364

Problem

给定一棵

n

个点的树，

q

次询问，每次给定

l,r,k

，查询：

\max\limits_{\substack{[l',r']\subseteq [l,r]\\r'-l'+1\ge k}} dep_{\operatorname{lca}([l',r'])}

的值。

1\le n,q\le 5\times 10^5

。

Solution

闲话：

场上 40min 写完，没调试，一发通过大样例！！！

杭师大机子极限数据 1.9s，应该能过吧？？？

Part 1

考虑一个类似于支配点对的东西，具体的，我们对于每个点

u

，我们找出他子树内的每一个极长连续段 $[l,r]$ ，并且满足 $\operatorname{lca}([l,r])=u$ 。

我们断言：这样子的点对

[l,r]

只有 $\mathcal{O}(n)$ 个。

证明：从子树合并角度来看太困难，我们不妨视作有一张图，每次子树合并的时候相当于会连接若干个 $(i,i+1)$ （也就是 $\operatorname{lca}(i,i+1)=u$ ），每连接一条会新产生一个极长段，我们会恰好连接 $n-1$ 次，所以最多只会有 $n+n-1=2n-1$ 个点对。

~~实时维护子树内的极长连续段，使用 dsu on tree 容易在 $\mathcal{O}(n\log{n})$ 复杂度内找出所有点对。~~

上面那个是本人在考场上写的东西，但是根据上面的证明，我们注意到其实存在更简单地找连续段地方法：

我们将一个操作 $\operatorname{link}(i,i+1)$ 挂在 $dep_{\operatorname{lca}(i,i+1)}$ 处，然后倒着扫描 $dep$ ，每次执行挂在这个深度的操作，时刻 维护连续段并加入支配点对集合 即可。

连续段可以使用并查集或者 set 维护，复杂度

\mathcal{O}(n\log{n})

。

或者有更简单地做法：构造序列

a_i=dep_{\operatorname{lca}(i,i+1)}

，求

a

的笛卡尔树则每个节点管辖的区间就是一个支配对。

Part 2

接下来问题变为：

给定若干个线段，线段带权，每次询问给定一个线段，查询和该线段交集不小于 $k$ 的所有线段中的权值最大值。

考虑所有能对询问

[l,r]

产生贡献的线段

[l',r']

长什么样子：

$l\le l'\le r\le r'$ 。
$l'\le l\le r'\le r$ 。
$l'\le l\le r\le r'$ 。
$l\le l'\le r'\le r$ 。

最后一种可以拍入前两种中，下面略去不谈，第三种显然合法，所以偏序关系只有 $l,r$ 两维，扫描线即可；剩下两种（下面以第一种为例）除了

l

和

r

外还有交集不小于

k

的偏序关系，看起来像是三维偏序，但我们仔细分析：

如果我们保证 $r'-l'+1\ge k$ ，则交集不小于 $k$ 实际上是 $r-l'+1\ge k\Rightarrow l'\le r-k+1$ 。

我们考虑从大到小扫描 $k$ ，每次把

([l',r'],d)

的值挂在左端点

l'

处，每次就是询问

[l,r-k+1]

的区间

\max

。

同理处理第二种情况，并且我们发现其实这样子顺手把第四种算好了。

这样子复杂度就是

\mathcal{O}((n+q)\log{n})

了。

Code

CPP

#include<bits/stdc++.h>
// #define int long long
// #pragma GCC optimize(3,"Ofast","inline")
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ll long long
#define bint __int128
#define ull unsigned long long
#define uint unsigned int
#define ld double
#define PII pair<int,int>
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
#define cl(f,x) memset(f,x,sizeof(f))
#define pcnt(x) __builtin_popcount(x)
#define lg(x) (31-__builtin_clz(x))
using namespace std;
void file_IO() {
    freopen("query.in","r",stdin);
    freopen("query.out","w",stdout);
}
bool M1;
namespace IO {
	char Is[(1<<21)+10],Os[(1<<21)+10];
	int Ipt,Opt;
	char gc() {
		if(Ipt==1<<21)
			Ipt=0;
		if(!Ipt)
			Is[fread(Is,1,1<<21,stdin)]=0;
		return Is[Ipt++];
	}
	void flush() {
		fwrite(Os,1,Opt,stdout);
		Opt=0;
	}
	void pc(char x) {
		if(Opt==1<<21)
			flush();
		Os[Opt++]=x;
	}
	int read() {
		int x=0,f=1;
		char ch=gc();
		while(ch<'0'||ch>'9') {
			if(ch=='-')
				f=-1;
			ch=gc();
		}
		while(ch<='9'&&ch>='0')
			x=(x<<3)+(x<<1)+ch-'0',ch=gc();
		return x*f;
	}
	int tt[100];
	void write(int x) {
		if(x<0)
			pc('-'),x=-x;
		if(!x) {
			pc('0');
			return;
		}
		int len=0;
		while(x)
			tt[++len]=x%10,x/=10;
		per(i,len,1)
			pc(tt[i]+48);
	}
}
using namespace IO;
const int INF=0x3f3f3f3f;
const ll INFLL=0x3f3f3f3f3f3f3f3f;
const ld eps=1e-9;
const int N=5e5+5;
int head[N],len;
struct node {
    int to,nxt;
}; node edge[N<<1];
void add_edge(int u,int v) {
    edge[++len]={v,head[u]}; head[u]=len;
}
int d[N],pa[N],max_son[N],siz[N];
void dfs(int u,int fa) {
	d[u]=d[fa]+1; pa[u]=fa;
	siz[u]=1;
	for(int i=head[u];i;i=edge[i].nxt) {
		int v=edge[i].to;
		if(v!=fa) {
			dfs(v,u);
			if(siz[v]>siz[max_son[u]])
				max_son[u]=v;
			siz[u]+=siz[v];
		}
	}
}
int top[N],dfn[N],p;
void dfs1(int u,int w) {
	top[u]=w; dfn[u]=++p;
	if(max_son[u])
		dfs1(max_son[u],w);
	for(int i=head[u];i;i=edge[i].nxt) {
		int v=edge[i].to;
		if(v!=max_son[u]&&v!=pa[u])
			dfs1(v,v);
	}
}
int lca(int u,int v) {
	while(top[u]!=top[v]) {
		if(d[top[u]]>d[top[v]])
			swap(u,v);
		v=pa[top[v]];
	}
	return d[u]<d[v]? u:v;
}
struct info {
    int l,r,k;
}; vector<info> vec[N],upd[N],ask[N],assk[N];
void ins(int l,int r,int v) {
    vec[r].push_back({l,r,v});
    upd[r-l+1].push_back({l,r,v});
}
struct dsu {
    int fa[N];
    void init(int n) {
        rep(i,1,n)
            fa[i]=i;
    }
    int find(int x) {
        if(fa[x]!=x)
            fa[x]=find(fa[x]);
        return fa[x];
    }
    void merge(int u,int v) {
        u=find(u); v=find(v);
        if(u!=v)
            fa[u]=v;
    }
    bool same(int u,int v) {
        return find(u)==find(v);
    }
}; dsu pre,suf;
void link(int k,int v) { //link(k,k+1)
    int l=pre.find(k),r=suf.find(k+1);
    ins(l,r,v);
    pre.merge(k+1,k);
    suf.merge(k,k+1);
}
vector<int> tmp[N];
struct SGT {
	struct node {
		int l,r,val;
	}; node tree[N<<2];
	#define ls(k) (k<<1)
	#define rs(k) (k<<1|1)
	void push_up(int k) {
		tree[k].val=max(tree[ls(k)].val,tree[rs(k)].val);
	}
	void build(int k,int l,int r) {
		tree[k].l=l; tree[k].r=r;
		if(l==r)
			return;
		int mid=(l+r)>>1;
		build(ls(k),l,mid);
		build(rs(k),mid+1,r);
	}
	void update(int k,int qx,int val) {
		if(tree[k].l==tree[k].r) {
			chkmax(tree[k].val,val);
			return;
		}
		if(qx<=tree[ls(k)].r)
			update(ls(k),qx,val);
		else
			update(rs(k),qx,val);
		push_up(k);
	}
	int query(int k,int ql,int qr) {
        if(ql>qr)
            return 0;
		if(ql<=tree[k].l&&tree[k].r<=qr)
			return tree[k].val;
		int res=0;
		if(ql<=tree[ls(k)].r)
			chkmax(res,query(ls(k),ql,qr));
		if(qr>=tree[rs(k)].l)
			chkmax(res,query(rs(k),ql,qr));
		return res;
	}	
	#undef ls
	#undef rs
}; SGT T1,T2,T3;
int ans[N];
void solve() {
    int n=read();
    rep(i,2,n) {
        int u=read(),v=read();
        add_edge(u,v);
        add_edge(v,u);
    }
    dfs(1,0);
    dfs1(1,1);
    rep(i,1,n-1)
        tmp[d[lca(i,i+1)]].push_back(i);
    pre.init(n);
    suf.init(n);
    rep(i,1,n)
        ins(i,i,d[i]);
    per(i,n,1) {
        for(auto x:tmp[i])
            link(x,i);
    }
    int q=read();
    rep(i,1,q) {
        int l=read(),r=read(),k=read();
        assk[r].push_back({l,r,i});
        ask[k].push_back({l,r,i});
    }
    T1.build(1,1,n);
    T2.build(1,1,n);
    per(i,n,1) {
        for(auto x:upd[i]) {
            int l=x.l,r=x.r,k=x.k;
            T1.update(1,l,k);
            T2.update(1,r,k);
        }
        for(auto x:ask[i]) {
            int l=x.l,r=x.r,k=x.k;
            chkmax(ans[k],T1.query(1,l,r-i+1));
            chkmax(ans[k],T2.query(1,l+i-1,r));
        }
    }
    T3.build(1,1,n);
    per(i,n,1) {
        for(auto x:vec[i])
            T3.update(1,x.l,x.k);
        for(auto x:assk[i])
            chkmax(ans[x.k],T3.query(1,1,x.l));
    }
    rep(i,1,q)
        write(ans[i]),pc('\n');
    flush();
}
bool M2;
// g++ query.cpp -std=c++14 -Wall -O2 -o query
signed main() {
    file_IO();
    int testcase=1;
    // scanf("%d",&testcase);
    while(testcase--)
        solve();
    debug("used time = %dms\n",(signed)(1000*clock()/CLOCKS_PER_SEC));
    debug("used memory = %dMB\n",(signed)((&M1-&M2)/1024/1024));
    return 0;
}

文章操作