题解--布尔

· · 题解

简要题意：问区间能最少划分成段，每一段 2-SAT 判断为 1。

10~40pts

很明显需要维护一个 f 数组，f_i=k 代表 [i,k] 这段区间非法且 k 最小，然后用倍增跳。直接对于每个 i 暴力求出 f_i 即可。
求的方法是用 2-SAT，每次 u\rightarrow v,v\rightarrow u,u'\rightarrow v',v'\rightarrow u'。
当然由于连的是双向边可以把 tarjan 换成并查集。

100pts

进行分析，发现 f 数组具有决策单调性。简要证明一下：我们考虑从右往左看，每次会新加入一条边，也就更有可能在更近的地方非法，而且不可能在更远的地方达到第一个非法点，所以 f_i\le f_j(i<j)。二分单调队列/单调栈很明显不好维护这个信息，我们考虑用整体二分去求。
定义 cal(l,r,L,R) 代表当前是 l,r 区间，f_i\in [L,R](i\in [l,r])。递归时往 cal(l,mid-1,L,f_{mid}) 和 cal(mid+1,r,f_{mid},R) 这样就可以用一个并查集进行撤销和继承。
求 f_{mid} 的时候从 L 开始一直加边，加到非法为止。注意有可能加到末尾依然合法，需要特判。
非法的判定可以用加边后 u,u' 是否连通来判断。考虑反证法，若存在 w,w' 在加边后连通，且 u,u' 不连通，那么 w,w' 分别与 u 和 v 或者 u' 和 v' 连通。根据我们的连边方式，若 u,v 连通则 u',v' 连通。所以 u,u' 连通。
时间复杂度 O(m\log m\log n+q\log m)。具体实现可以看代码。 

#include<bits/stdc++.h>
using namespace std;
const int maxn=6e5+5,maxm=1e5+5;
char __buf[1<<21],*__p1,*__p2;
#define getchar() (__p1==__p2?(__p2=__buf+fread(__p1=__buf,1,1<<21,stdin),__p1==__p2?EOF:*__p1++):*__p1++)
inline int read() {
    int __x=0;
    char __c=getchar();
    while(__c<'0'||__c>'9') __c=getchar();
    while(__c>='0'&&__c<='9') {
        __x=__x*10+__c-'0';
        __c=getchar();
    }
    return __x;
}
inline char pc(char ch,bool bj) {
    static char buf[1<<18],*p1=buf,*p2=buf+(1<<18);
    return ((bj)||(*p1++=ch)&&p1==p2)&&fwrite(p1=buf,1,p1-buf,stdout),0;
}
void print(int x) {
    if(x<0)x=-x,pc('-',0);
    if(x>9)print(x/10);
    pc(x%10^48,false);
}
inline void printnum(int x,int ch) {
    print(x),pc(ch,false);
}
struct oper {
    int op,x,y;
    oper() {}
    oper(int Op,int X,int Y) {
        op=Op,x=X,y=Y;
    }
} o[maxn*4];
int u[maxn],v[maxn],oc,n,m,ans[maxn],f[maxm*2],siz[maxm*2],q,g[maxn][20],zm[maxn];
int getf(int x) {
    return f[x]==x?x:getf(f[x]);
}
int opp(int x) {
    return x&1?x+1:x-1;
}
void merge(int x,int y) {
    x=getf(x),y=getf(y);
    if(x==y)return;
    if(siz[x]<siz[y])swap(x,y);
    o[++oc]=oper(0,y,0),f[y]=x;
    o[++oc]=oper(1,x,siz[y]),siz[x]+=siz[y];
}
void replace(int cas) {
    while(oc>cas) {
        int op=o[oc].op,x=o[oc].x,y=o[oc].y;
        if(!op)f[x]=x;
        if(op==1)siz[x]-=y;
        oc--;
    }
}
bool check(int x) {
    return getf(x)==getf(opp(x));
}
void solve(int l,int r,int L,int R,bool lst) {
    if(L==R) {
        for(register int i=l; i<=r; i++)ans[i]=L;
        return;
    }
    if(l>r)return;
    int mid=(l+r)/2,cas=oc;
    bool now=lst;
    for(register int i=mid; i<=r&&i<L; i++) {
        merge(u[i],v[i]),merge(opp(u[i]),opp(v[i]));
        now|=check(u[i]);
        if(now)break;
    }//mid~min(r,L-1) 的边是一定要用的，先加上
    int tmp=oc,sum=now;
    for(register int i=max(L,mid); i<=R; i++) {
        merge(u[i],v[i]),merge(opp(u[i]),opp(v[i]));
        now|=check(u[i]);
        if(now) {
            ans[mid]=i;
            break;
        }
    }//从 max(L,mid) 一直加到 R 来寻找 mid 处答案
    bool pd=0;
    if(!ans[mid]) {
        ans[mid]=m+1;
        for(register int i=mid+1; i<=r; i++)ans[i]=m+1;
        pd=1;
    }//如果到最右边仍然合法，那么它的右区间也合法
    replace(tmp);
    solve(l,mid-1,L,ans[mid],sum);//l~mid-1 需要 mid~min(r,L-1) 的边
    replace(cas);
    if(pd)return;
    now=lst;
    for(register int i=max(r+1,L); i<ans[mid]; i++) {
        merge(u[i],v[i]),merge(opp(u[i]),opp(v[i]));
        now|=check(u[i]);
        if(now)break;
    }
    solve(mid+1,r,ans[mid],R,now);//mid+1,~r 需要 max(r+1,L)~ans[mid]-1 的边
    replace(cas);
}
int main() {
    int U,x,V,y;
    bool p=0;
    n=read(),m=read(),q=read();
    for(register int i=1; i<=2*n; i++)f[i]=i,siz[i]=1;
    for(register int i=1; i<=m; i++) {
        U=read(),x=read(),V=read(),y=read();
        zm[i]=zm[i-1]+(U==V&&x!=y);
        u[i]=U*2-1+x,v[i]=V*2-1+y;
        merge(u[i],v[i]),merge(opp(u[i]),opp(v[i]));
        p|=check(u[i]);
    }
    if(!p) {
        while(q--)printnum(1,'\n');
        return pc(0,1),0;
    }
    replace(0);
    u[m+1]=1,v[m+1]=2;
    solve(1,m,1,m+1,0);
    for(register int i=0; i<20; i++)g[m+1][i]=m+1;
    for(register int i=m; i; i--) {
        g[i][0]=ans[i];
        for(register int j=1; j<20; j++)g[i][j]=g[g[i][j-1]][j-1];
    }
    while(q--) {
        x=read(),y=read();
        if(zm[y]-zm[x-1]>0) {
            printnum(-1,'\n');
            continue;
        }
        int w=1;
        for(register int i=19; i>=0; i--)
            if(g[x][i]<=y)x=g[x][i],w+=(1<<i);
        printnum(w,'\n');
    }
    pc(0,1);
    return 0;
}