P11364
lsj2009
·
·
题解
Problem
给定一棵 n 个点的树，q 次询问，每次给定 l,r,k，查询：
\max\limits_{\substack{[l',r']\subseteq [l,r]\\r'-l'+1\ge k}} dep_{\operatorname{lca}([l',r'])}
的值。
## 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']$ 长什么样子：
1. $l\le l'\le r\le r'$。
2. $l'\le l\le r'\le r$。
3. $l'\le l\le r\le r'$。
4. $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;
}
```