题目概述

有 $m$ 条边，每条双向边 $(x_i,y_i)$ 只有人数在 $[l_i,r_i]$ 时才能通过，如果人数 $x$ 能够从 $1$ 到 $n$ 则可行，求可行的 $x$ 的数量。

解题报告

超级套路题，首先我们把 $[l_i,r_i]$ 离散去重一下，如果相邻两个元素 $X_i,X_{i+1}$ 差距 $X_{i+1}-X_i>1$ ，就在两者之间添加一个权重为 $X_{i+1}-X_i-1$ 的点表示他们的中间状态。

把每条边分配到线段树上，然后在线段树上分治，用并查集按秩合并的回退特性维护每个节点的连通情况就行了。

示例程序

#include<cstdio>
#include<cctype>
#include<vector>
#include<algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
const int maxn=100000,maxm=400000;

int n,m,X[maxn+5],Y[maxn+5],A[maxn+5],B[maxn+5];
int tem[maxm+5],c[maxm+5],w[maxm+5],sum[maxm+5],ans;
vector< pair<int,int> > e[(maxm<<2)+5];
int fat[maxn+5],dep[maxn+5],top;vector< pair<int*,int> > stk;

#define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    lst=='-'?x=-tot:x=tot;return EOLN(ch);
}
int Find(int x){
    for (int L=1,R=c[0],mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1))
        if (x==c[mid]) return mid; else x<c[mid]?R=mid-1:L=mid+1;
}
void Insert(int L,int R,int ID,int l=1,int r=c[0],int p=1){
    if (L==l && r==R) {e[p].push_back(mp(X[ID],Y[ID]));return;} int mid=l+(r-l>>1);
    if (R<=mid) Insert(L,R,ID,l,mid,p<<1); else if (L>mid) Insert(L,R,ID,mid+1,r,p<<1|1);
    else Insert(L,mid,ID,l,mid,p<<1),Insert(mid+1,R,ID,mid+1,r,p<<1|1);
}
int getfa(int x) {return x==fat[x]?x:getfa(fat[x]);}
void Change(int *x,int y) {top++;stk.push_back(mp(x,*x));*x=y;}
void Merge(int x,int y){
    x=getfa(x);y=getfa(y);if (x==y) return;
    if (dep[x]<dep[y]) swap(x,y);
    if (dep[x]==dep[y]) Change(&dep[x],dep[x]+1);
    Change(&fat[y],x);
}
void Pop(int lst) {while (top!=lst) *stk[top-1].fr=stk[top-1].sc,stk.pop_back(),top--;}
void Solve(int L,int R,int p=1){
    int lsttop=top,mid=L+(R-L>>1);
    for (int si=e[p].size(),i=0;i<si;i++) Merge(e[p][i].fr,e[p][i].sc);
    if (getfa(1)==getfa(n)) {ans+=sum[R]-sum[L-1];Pop(lsttop);return;}
    if (L==R) {Pop(lsttop);return;}
    Solve(L,mid,p<<1);Solve(mid+1,R,p<<1|1);Pop(lsttop);
}
int main(){
    freopen("E.in","r",stdin);freopen("E.out","w",stdout);
    readi(n);readi(m);
    for (int i=1;i<=m;i++){
        readi(X[i]);readi(Y[i]);readi(A[i]);readi(B[i]);
        tem[++tem[0]]=A[i];tem[++tem[0]]=B[i];
    }
    sort(tem+1,tem+1+tem[0]);tem[0]=unique(tem+1,tem+1+tem[0])-(tem+1);
    for (int i=1;i<=tem[0];i++){
        c[++c[0]]=tem[i];w[c[0]]=1;
        if (i<tem[0] && tem[i]+1<tem[i+1]) c[++c[0]]=tem[i]+1,w[c[0]]=tem[i+1]-tem[i]-1;
    }
    for (int i=1;i<=c[0];i++) sum[i]=sum[i-1]+w[i];
    for (int i=1;i<=m;i++) Insert(Find(A[i]),Find(B[i]),i);
    for (int i=1;i<=n;i++) fat[i]=i;
    Solve(1,c[0]);printf("%d\n",ans);return 0;
}