#include #define rep(i,a,b) for(int i=(a);i<=(b);++i) #define per(i,a,b) for(int i=(a);i>=(b);--i) #define pb push_back #define fi first #define sc second using namespace std; typedef pair pii; typedef long long LL; bool _ST; //类似魔法少女网站的做法,找到极大区间合并,然后dsu一下就知道 $O(n\log n)$ 段有效区间 L,R,len,dep //按 len 排序,查询 len>=k ,L\in [l,r-k+1] 的最大的 dep //还有,这个可以按 l 扫描线查询后缀 max L<=l,R>=l+k-1 的最大 dep //现在可以做到 $O(n\log^2 n+m\log n)$ //80+eps,如果 dsu 没卡满,显然一层中同一 L 只用最大的 len,盲猜卡不满是单log template void read(T &x){ x=0;char c=getchar(); while(c<'0'||c>'9') c=getchar(); while('0'<=c&&c<='9'){x=(x<<1)+(x<<3)+(c&15);c=getchar();} } const int N=5e5+100; int n,q,siz[N],dep[N],son[N],pos[N],idx,ans[N],maxx[N]; vector E[N],node[N]; struct QUE{int l,r,k,id;}; vector qu1[N]; vector opt1[N],opt2[N],qu2[N]; struct LIST{//链表 int fa[N],ls[N],rs[N]; bool vis[N]; void init(){ rep(i,1,n) ls[i]=i,rs[i]=i,fa[i]=i,vis[i]=0; } int getf(int x){return x==fa[x]?x:fa[x]=getf(fa[x]);} void merge(int x,int y){ x=getf(x),y=getf(y); if(x==y) return; fa[y]=x,ls[x]=min(ls[x],ls[y]),rs[x]=max(rs[x],rs[y]); } void insert(int x,int di){ vis[x]=1,ls[x]=rs[x]=x; if(vis[x-1]) merge(x,x-1); if(vis[x+1]) merge(x,x+1); //ls[x],rs[x]-ls[x]+1,di //ls[x],rs[x],di int rr=rs[getf(x)],ll=ls[getf(x)]; opt1[rr-ll+1].pb({ll,di}); opt2[ll].pb({rr,di}); } void del(int x){ vis[x]=0,ls[x]=rs[x]=fa[x]=x; } }TR; void dfs1(int x,int ff){ dep[x]=dep[ff]+1,siz[x]=1; for(auto y:E[x]) if(y!=ff){ dfs1(y,x); siz[x]+=siz[y]; if(siz[y]>siz[son[x]]) son[x]=y; } } void dfs2(int x,int ff){ for(auto y:E[x]) if(y!=son[x]&&y!=ff){ dfs2(y,x); for(auto i:node[pos[y]]) TR.del(i); } if(son[x]) dfs2(son[x],x); pos[x]=son[x]?pos[son[x]]:++idx; TR.insert(x,dep[x]),node[pos[x]].pb(x); for(auto y:E[x]) if(y!=son[x]&&y!=ff){ for(auto i:node[pos[y]]) { TR.insert(i,dep[x]),node[pos[x]].pb(i); } node[pos[y]].clear(),node[pos[y]].shrink_to_fit(); } } int mx[N<<2]; #define ls(x) x<<1 #define rs(x) x<<1|1 void update(int x,int l,int r,int u){ if(l==r) return mx[x]=maxx[l],void(); int mid=l+r>>1; (mid>=u)?update(ls(x),l,mid,u):update(rs(x),mid+1,r,u); mx[x]=max(mx[ls(x)],mx[rs(x)]); } int query(int x,int l,int r,int L,int R){ if(L<=l&&r<=R) return mx[x]; int mid=l+r>>1,res=0; if(mid>=L) res=query(ls(x),l,mid,L,R); if(mid(y=dfn[y])) swap(x,y); int k=__lg(y-x++); return gmin(mi[k][x],mi[k][y-(1<