jzoj 4240.【五校联考5day2】游行 主席树优化连边+支配树
Description
恶梦是学校里面的学生会主席。他今天非常的兴奋，因为学校一年一度的学生节开始啦！！
在这次节日上总共有N个节目，并且总共也有N个舞台供大家表演。其中第i个节目的表演时间为第i个单位时间,表演的舞台为Ai,注意可能有多个节目使用同一个舞台。
作为恶梦的忠实粉丝之一的肥佬，当然要来逛一下啦，顺便看一下能不能要到恶梦的签名。
肥佬一开始会先在A1 看完节目1再去闲逛。
肥佬可以在舞台之间随便乱走。但是假如肥佬当前在看第i个节目，站在第Ai个舞台前面的话，由于有些道路被*了，所以肥佬下一步只能前往第Li到第Ri个舞台中的一个。并且当一个节目结束的时候，肥佬只能去看另外一个节目，或者结束自己的闲逛。
具体而言就是说，假设肥佬可以从第i个节目走去第j个节目，那么当且仅当i<j且Li <= Aj <= Ri。
但事实上是，恶梦非常讨厌被自己的粉丝跟踪。所以他想在只*掉一个节目的情况下，使得肥佬不能到达自己所在的地方。并且为了防止意外，他还想知道有多少个这样的节目。
简而言之，恶梦想知道对于任意一个节目p∈[1,N],有多少个节目t,使得删掉t之后，不存在一条从节目1出发到节目p的路径。注意，节目1和节目p也是可以被删的。
由于他非常的忙碌，所以他把这个任务交给了你。
Input
第一行包括一个正整数N,表示总共有N个节目。
第二行包括N个正整数Ai,表示第i个节目占用了第Ai个舞台。
接下来的N行,第i行包括两个正整数Li,Ri,表示第i个节目的路径限制。
Output
总共N行。第i行包括一个整数c,表示当恶梦站在第i个节目的时候，有多少个满足要求的节点。
特别的，若一开始就不存在从1出发到i的路径的话，你需要输出-1.
Sample Input
10
1 6 1 8 7 2 3 9 10 10
5 8
2 4
1 2
9 10
8 9
9 9
10 10
2 2
2 4
9 9
Sample Output
1
2
-1
2
2
3
3
2
2
2
Data Constraint
对于15%的数据,N <= 100
对于30%的数据,N <= 800
对于50%的数据,N <= 5000
对于70%的数据,N <= 10000
对于100%的数据,N <= 50000
Hint
样例解释：
我们假如将一个节目视为一个节点的话，按题意所述，我们可以构造出一副有向图。
设对于点i,他可选的删除集合为Si
那么很直观的就可以看出来:
对于1号节点，S1 = {1}
对于2号节点，S2 = {1,2}
对于3号节点，由于本来就不存在1到3的路径，所以应输出-1
对于4号节点，S4 = {1,4}
对于5号节点，S5 = {1,5}
对于6号节点，S6 = {1,2,6}
对于7号节点，S7 = {1,2,7}
对于8号节点，S8 = {1,8},5号点和6号点都不是合法的点。
对于9号节点，S9 = {1,9}
对于10号节点，S10 = {1,10}
分析：
显然就是求每个点的支配点的个数。
这题是一个有向无环图，显然只有前面的节目可以连后面的节目，可以使用lca的方法求支配。不过我直接写了有向图的支配树。
这题边数特别多，但注意连边的舞台到是一个区间，考虑倍增或者线段树连边。
这题考虑以舞台编号为下标建线段树。从后面节目往前面做，对于一个节目，我们把的节目挂在对应舞台的叶子节点上。假设一个节目舞台是，就挂在代表那个节点上。那么节目连的边只有条。但是当往前做时，树的叶子节点会出现变化，导致后面的节目受到影响，所以我们只能可持久化线段树来优化连边。
每次我们增加一条链，对于这条链的叶子节点，挂上当前的节目，并向更新前的这个叶子节点连边，继承前面已经挂在这个点的其他节目，剩下的边就只是线段树的边了。
代码：
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
const int N=5e4+7;
using namespace std;
int n,m,cnt,tot;
int ls[N*20],f[N*20];
int a[N],x[N],y[N],root[N];
struct node{
int l,r;
}t[N*20];
struct edge{
int y,next;
}g[N*100];
struct DMT{
vector <int> pre[N*20],dom[N*20];
int dfn[N*20],fa[N*20],id[N*20],idom[N*20],sdom[N*20],p[N*20],val[N*20];
void dfs(int x)
{
dfn[x]=++cnt;
id[cnt]=x;
for (int i=ls[x];i>0;i=g[i].next)
{
int y=g[i].y;
pre[y].push_back(x);
if (!dfn[y])
{
fa[y]=x;
dfs(y);
}
}
}
int get(int x)
{
if (p[x]==x) return x;
int y=get(p[x]);
if (dfn[sdom[val[p[x]]]]<dfn[sdom[val[x]]]) val[x]=val[p[x]];
return p[x]=y;
}
int smin(int x,int y)
{
if (dfn[x]<dfn[y]) return x;
return y;
}
void build()
{
for (int i=cnt;i>0;i--)
{
int x=id[i];
if (!pre[x].empty())
{
for (int j=0;j<pre[x].size();j++)
{
int y=pre[x][j];
if (dfn[y]<dfn[x]) sdom[x]=smin(sdom[x],y);
else
{
get(y);
sdom[x]=smin(sdom[x],sdom[val[y]]);
}
}
}
pre[x].clear();
p[x]=fa[x];
dom[sdom[x]].push_back(x);
if (!dom[fa[x]].empty())
{
for (int j=0;j<dom[fa[x]].size();j++)
{
int y=dom[fa[x]][j];
get(y);
int d=val[y];
if (dfn[sdom[d]]>=dfn[sdom[y]]) idom[y]=sdom[y];
else idom[y]=d;
}
dom[fa[x]].clear();
}
}
for (int i=1;i<=cnt;i++)
{
int x=id[i];
if (idom[x]!=sdom[x]) idom[x]=idom[idom[x]];
f[x]=f[idom[x]]+(x<=n);
}
}
void solve()
{
for (int i=1;i<=m;i++) p[i]=val[i]=sdom[i]=i;
dfs(1);
build();
}
}T;
void add(int x,int y)
{
g[++tot]=(edge){y,ls[x]};
ls[x]=tot;
}
void ins(int &p,int q,int l,int r,int x,int num)
{
if (!p) p=++cnt;
if (l==r)
{
if (q) add(p+n,q+n);
add(p+n,num);
return;
}
int mid=(l+r)/2;
if (x<=mid) t[p].r=t[q].r,ins(t[p].l,t[q].l,l,mid,x,num);
else t[p].l=t[q].l,ins(t[p].r,t[q].r,mid+1,r,x,num);
if (t[p].l) add(p+n,t[p].l+n);
if (t[p].r) add(p+n,t[p].r+n);
}
void add_edge(int p,int l,int r,int x,int y,int num)
{
if (!p) return;
if ((l==x) && (r==y))
{
add(num,p+n);
return;
}
int mid=(l+r)/2;
if (y<=mid) add_edge(t[p].l,l,mid,x,y,num);
else if (x>mid) add_edge(t[p].r,mid+1,r,x,y,num);
else
{
add_edge(t[p].l,l,mid,x,mid,num);
add_edge(t[p].r,mid+1,r,mid+1,y,num);
}
}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
for (int i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]);
for (int i=n;i>1;i--)
{
ins(root[i],root[i+1],1,n,a[i],i);
add_edge(root[i],1,n,x[i-1],y[i-1],i-1);
}
m=n+cnt;
cnt=0;
T.solve();
for (int i=1;i<=n;i++)
{
if (!f[i]) printf("-1\n");
else printf("%d\n",f[i]);
}
}