题目背景
SOURCE：NOIP2015-GDZSJNZX（难）
题目描述
学校一年一度的学生艺术节开始啦！在这次的艺术节上总共有 N 个节目，并且总共也有 N 个舞台供大家表演。其中第 i 个节目的表演时间为第 i 个单位时间，表演的舞台为 Ai ，注意可能有多个节目使用同一个舞台。作为 Tom 的忠实粉丝之一的 Alice，当然要来逛一下啦，顺便看一下能不能要到 Tom 的签名。
Alice 一开始会先在 A1 看完节目1再去闲逛。
Alice 可以在舞台之间随便乱走。但是假如 Alice 当前在看第 i 个节目，站在第 Ai 个舞台前面的话，由于有些道路被封锁了，所以Alice 下一步只能前往第 Li～Ri 个舞台中的一个。并且当一个节目结束的时候，Alice 只能去看另外一个节目，或者结束自己的闲逛。
具体而言就是说，假设 Alice 可以从第 i 个节目走去第 j 个节目，那么当且仅当 i<ji<ji<j 且 Li≤Aj≤Ri 。
但事实上是，Tom 非常讨厌被自己的粉丝跟踪。所以他想在只封锁掉一个节目的情况下，使得 Alice 不能到达自己所在的地方。并且为了防止意外，他还想知道有多少个这样的节目。
简而言之，Tom 想知道对于任意一个节目 p∈[1,N] ，有多少个节目 t ，使得删掉 t 之后，不存在一条从 节目1 出发到 节目p 的路径。注意，节目1 和 节目p 也是可以被删的。由于他非常的忙碌，所以他把这个任务交给了你。
输入格式
第一行包括一个正整数 N ，表示总共有 N 个节目。
第二行包括 N 个正整数 Ai ，表示第 i 个节目占用了第 Ai 个舞台。
接下来的 N 行，第 i 行包括两个正整数 Li，Ri，表示第 i 个节目的路径限制。
输出格式
总共 N 行。第 i 行包括一个整数 c ，表示当 Tom 站在第 i 个节目的时候，有多少个满足要求的节点。
特别的，若一开始就不存在从 1 出发到 i 的路径的话，你需要输出 -1 。
样例数据 1
输入
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
输出
1
2
-1
2
2
3
3
2
2
2
备注
【样例解释】
我们假如将一个节目视为一个节点的话，按题意所述，我们可以构造出一副有向图。
设对于点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}
【数据范围】
对于 15% 的数据，N≤100
对于 30% 的数据，N≤800
对于 50% 的数据，N≤5000
对于 70% 的数据，N≤10000
对于 100% 的数据，N≤50000
首先这题我们要用到一个叫做支配树（dominatordominatordominator treetreetree）的东西，还有一个叫做主席树的东西。如果不会的请自行百度，如果只想了解支配树在DAG上的姿势请戳这里
那么在学习了dominatordominatordominator treetreetree 过后，我们继续解决这道题吧。
我们从000分算法开始分析
000分算法：
随便写一个瞎暴力（略）
151515分算法：
我们显然可以O（n2）O（n^2）O（n2）建图，枚举终点和断点i,ji,ji,j，再暴力判断断掉jjj后是否存在1−>i1->i1−>i的路径
303030分算法：
将151515分算法进行优化，构图仍然可以O（n2）O（n^2）O（n2），我们只需改改统计必经点个数的算法，怎么做呢？
我们直接枚举必经点jjj,然后直接从起点sss开始dfsdfsdfs，将没有访问到的点的答案个数加111即可。
505050分算法：
如果我们沿用前两种算法，计算答案的时间显然太长了，而且经过尝试我们不难发现不能使用tarjantarjantarjan算法来统计，这个时候我们就要用到我们刚刚补充的dominatordominatordominator treetreetree了，这样我们可以拿到505050分了
100100100分算法？
不难想到要改变建图的方式来改进时间效率：由于题目中有限制：i,ji,ji,j之间连边当且仅当i<ji<ji<j且Li≤Aj≤RiLi \le Aj\le RiLi≤Aj≤Ri，如果我们改变枚举建边的顺序，倒序从n−>1n->1n−>1建边，那么如果我们用主席树维护限制的区间[Li,Ri][Li,Ri][Li,Ri]，将AiAiAi看做是“单点修改”的值进行修改。
由于我们使用了主席树来维护，所以并不会有MLEMLEMLE这种事情发生。
那么假如现在要向Ti,L,RT_i,L,RTi,L,R中加入一个jjj，那么我们需要把Pi,L,RP_i,L,RPi,L,R连接到jjj，同样的，我们还需要把Pi,L,RP_i,L,RPi,L,R连接到剩下的属于Si,L,RS_i,L,RSi,L,R的节点，又因为我们可以发现Si,L,R−Si+1,L,R=jS_i,L,R−S_i+1,L,R=jSi,L,R−Si+1,L,R=j所以我们只需要把Pi,L,RP_i,L,RPi,L,R连接到Pi+1,L,RP_{i+1},L,RPi+1,L,R,显然原DAGDAGDAG中的连通性是不会改变的
贴贴代码：
#include<bits/stdc++.h>
#define N 900005
using namespace std;
int n,first[N],fa[N][21],dep[N],ans[N],du[N],stk[N],tot=0,m,maxn;
bool vis[N];
struct edge{int v,next;}e[N*5];
inline void add(int u,int v){
e[++tot].v=v;
e[tot].next=first[u];
first[u]=tot;
}
inline int lca(int u,int v){
if(dep[u]>dep[v])swap(u,v);
for(int i=maxn;i>=0;--i)if(dep[fa[v][i]]>=dep[u])v=fa[v][i];
if(u==v)return u;
for(int i=maxn;i>=0;--i)if(fa[v][i]!=fa[u][i])v=fa[v][i],u=fa[u][i];
return fa[v][0];
}
inline void bfs(){
queue<int>q;
q.push(1);
while(!q.empty()){
int x=q.front();
q.pop();
for(int i=first[x];i;i=e[i].next){
int v=e[i].v;
++du[v];
if(vis[v])continue;
vis[v]=1,q.push(v);
}
}
}
inline void sol(){
stack<int>s;
s.push(1);
while((1<<maxn)<=m)++maxn;
while(!s.empty()){
int x=s.top();
s.pop();
dep[x]=dep[fa[x][0]]+1;
ans[x]=ans[fa[x][0]]+(x<=n);
for(int i=1;i<=maxn;++i)fa[x][i]=fa[fa[x][i-1]][i-1];
for(int i=first[x];i;i=e[i].next){
int v=e[i].v;
if(!fa[v][0])fa[v][0]=x;
else fa[v][0]=lca(x,fa[v][0]);
if(!(--du[v]))s.push(v);
}
}
for(int i=1;i<=n;++i){
if(dep[i])printf("%d\n",ans[i]);
else printf("-1\n");
}
}
struct Node{int l,r;}T[N];
int rt[N],l[N],r[N],a[N],pos=0;
inline long long read(){
long long ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+ch-'0',ch=getchar();
return ans;
}
inline void build(int p,int u,int l,int r,int ql,int qr){
if(p==0)return;
if(qr<l||ql>r)return;
if(ql<=l&&r<=qr){add(u,p+n);return;}
int mid=l+r>>1;
build(T[p].l,u,l,mid,ql,qr);
build(T[p].r,u,mid+1,r,ql,qr);
}
inline void update(int p,int &o,int v,int l,int r,int val){
o=++pos;
T[o]=T[p];
if(p)add(o+n,p+n);
add(o+n,v);
if(l==r)return;
int mid=l+r>>1;
if(val<=mid)update(T[p].l,T[o].l,v,l,mid,val);
else update(T[p].r,T[o].r,v,mid+1,r,val);
}
int main(){
n=read();
for(int i=1;i<=n;++i)a[i]=read();
for(int i=1;i<=n;++i)l[i]=read(),r[i]=read();
for(int i=n;i;--i){
build(rt[i+1],i,1,n,l[i],r[i]);
update(rt[i+1],rt[i],i,1,n,a[i]);
}
m=n+pos;
bfs();
sol();
return 0;
}