脚本宝典收集整理的这篇文章主要介绍了[冲刺国赛2022] 模拟赛1，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
题目描述
给定一棵有根树，根是 (1)，顶点编号是 (1,2...n)，对于 (2leq ileq n) 有 (f_i) 是 (i) 的父亲，(a_1...a_n) 是 (1...n) 的一个排列。
有 (m) 次询问，每次询问给出 (l,r)，问有多少个二元组 (L,R)，满足 (lleq Lleq Rleq r)，且对任意 (Lleq a_xleq a_yleq R)，满足树上的最近公共祖先 (z) 满足 (Lleq a_zleq R)
(n,mleq 2cdot 10^5)
解法
从整体的角度来考虑限制，也就是任取两个点 (x,y) ，如果 (xleq zleq y)，那么 ((x,y)) 对所有 ((l,r)) 的合法性没有影响；如果 (z<xleq y)，那么它会使得 (lin(z,x],rin[y,n]) 的 ((l,r)) 不合法；如果 (xleq y<z)，那么它会使得 (lin[1,x],rin[y,z)) 的 ((l,r)) 不合法。
那么问题变成了有若干个矩形，我们不能取矩形中的点，每次问一个范围中可以取的点数是多少。
首先要减少矩形的数量，发现可以在 (z) 处统计所有的矩形，而且可以用树上启发式合并，根据包含关系在把某个点合并上来时只用考虑其前驱后继（与之类似的题目：事情的相似度）
剩下的就是套路了，我们移动右端点，维护所有左端点的历史答案和。线段树要支持历史零点个数查询，我们只需要额外维护标记序列的最小值和取到这个最小值的数量即可，时间复杂度 (O(nlog^2n))
总结
本题最出彩的地方是表示限制的方法，这种小处到整体的技巧很类似于贡献法。我一开始想虚树是不行的，因为本题不同 ((l,r)) 的合法性之间有很大的联系，我没有利用到。
#include <cstdio>
#include <vector>
#include <iostream>
#include <set>
using namespace std;
const int M = 200005;
const int N = M<<2;
#define pb push_back
#define ll long long
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
void write(ll x)
{
if(x>=10) write(x/10);
putchar(x%10+'0');
}
int n,m,a[M],mi[N],mc[N],fl[N],ti[N],tc[N];
vector<int> g[M];set<int> s[M];ll ans[M],sum[N];
struct node{int l,r,c;};vector<node> v[M],q[M];
void add(int x,int y,int z)
{
if(x<=z && z<=y) return ;
if(z<x) v[y].pb({z+1,x,1});
else v[y].pb({1,x,1}),v[z].pb({1,x,-1});
}
void dfs(int u,int fa)
{
s[u].insert(a[u]);
for(int &v:g[u]) if(v^fa)
{
dfs(v,u);
if(s[u].size()<s[v].size())
swap(s[u],s[v]);
for(int x:s[v])
{
auto it=s[u].lower_bound(x);
if(it!=s[u].end()) add(x,*it,a[u]);
if(it!=s[u].begin()) it--,add(*it,x,a[u]);
}
for(int x:s[v]) s[u].insert(x);
}
}
void up(int i)
{
mi[i]=min(mi[i<<1],mi[i<<1|1]);mc[i]=0;
if(mi[i]==mi[i<<1]) mc[i]+=mc[i<<1];
if(mi[i]==mi[i<<1|1]) mc[i]+=mc[i<<1|1];
sum[i]=sum[i<<1]+sum[i<<1|1];
}
void build(int i,int l,int r)
{
if(l==r)
{
mi[i]=mc[i]=1;
return ;
}
int mid=(l+r)>>1;
build(i<<1,l,mid);
build(i<<1|1,mid+1,r);
up(i);
}
void down(int i)
{
int ls=i<<1,rs=i<<1|1;
//
if(mi[ls]+ti[i]==0) sum[ls]+=1ll*tc[i]*mc[ls];
mi[ls]+=fl[i];
if(ti[i]+fl[ls]<ti[ls])
ti[ls]=ti[i]+fl[ls],tc[ls]=0;
if(ti[i]+fl[ls]==ti[ls]) tc[ls]+=tc[i];
fl[ls]+=fl[i];
//
if(mi[rs]+ti[i]==0) sum[rs]+=1ll*tc[i]*mc[rs];
mi[rs]+=fl[i];
if(ti[i]+fl[rs]<ti[rs])
ti[rs]=ti[i]+fl[rs],tc[rs]=0;
if(ti[i]+fl[rs]==ti[rs]) tc[rs]+=tc[i];
fl[rs]+=fl[i];
//
ti[i]=tc[i]=fl[i]=0;
}
void add(int i,int l,int r,int L,int R,int c)
{
if(L>r || l>R) return ;
if(L<=l && r<=R)
{
mi[i]+=c;fl[i]+=c;
if(mi[i]==0) sum[i]+=mc[i];
if(fl[i]<ti[i]) ti[i]=fl[i],tc[i]=0;
if(fl[i]==ti[i]) tc[i]++;
return ;
}
int mid=(l+r)>>1;down(i);
add(i<<1,l,mid,L,R,c);
add(i<<1|1,mid+1,r,L,R,c);
up(i);
}
int ask(int i,int l,int r,int L,int R)
{
if(L>r || l>R) return 0;
if(L<=l && r<=R) return sum[i];
int mid=(l+r)>>1;down(i);
return ask(i<<1,l,mid,L,R)
+ask(i<<1|1,mid+1,r,L,R);
}
signed main()
{
freopen("b.in","r",stdin);
freopen("b.out","w",stdout);
n=read();m=read();
for(int i=1;i<=n;i++) a[i]=read();
for(int i=2;i<=n;i++)
g[read()].pb(i);
dfs(1,0);
for(int i=1;i<=n;i++) v[i].pb({i,i,-1});//在 r=i 时激活 l=i
build(1,1,n);
for(int i=1;i<=m;i++)
{
int l=read(),r=read();
q[r].pb({l,r,i});
}
for(int i=1;i<=n;i++)
{
add(1,1,n,1,n,1);
for(auto &x:v[i])
add(1,1,n,x.l,x.r,x.c);
add(1,1,n,1,n,-1);//前面保证>=1，只在这里做一次历史
for(auto &x:q[i])
ans[x.c]+=ask(1,1,n,x.l,x.r);
}
for(int i=1;i<=m;i++)
write(ans[i]),puts("");
}
以上是脚本宝典为你收集整理的[冲刺国赛2022] 模拟赛1全部内容，希望文章能够帮你解决[冲刺国赛2022] 模拟赛1所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。