题解 P7871 【「Wdoi-4」芙兰的贤者时间】

· · 题解

题解

简化题面

根据题意，在第 i 块贤者之石里的能量若会向左传递，当且仅当 w_{i-1}<w_{i+1}，因此我们从 i+1 向 i-1 连边；若会向右传递，当且仅当 w_{i-1}>w_{i+1}，因此我们从 i-1 向 i+1 连边。

可以发现，最终连出来的边里，只会是奇数编号的点连向奇数编号的点、偶数编号的点连向偶数编号的点。考虑分为奇偶两块来考虑。又能发现，单独抽出奇数/偶数的节点，那么这些边连出来的必然是链的形状。

\boxed{1} \leftarrow \boxed{2} \phantom{\leftrightarrow} \boxed{3} \rightarrow \boxed{4} \leftarrow \boxed{5} \leftrightarrows \boxed{6}

对于这张图，可以发现由于 w_5>w_6,w_6>w_5 产生了矛盾，因此必然无解。

那么考虑，如果一张图有解，我们怎么确定它的最小字典序呢？

使用贪心。从左往右考虑每个点能被标注的最小的值。使用 \mathit{cnt} 表示当前标注了编号的点的数目（下文构造方案可以证明，此时 1\sim \mathit{cnt} 的标号都被用过了）。但是可能出现如下状况：

\boxed{1} \rightarrow \boxed{2} \rightarrow \boxed{3} \leftarrow \boxed{4}

如果我们把 1 标为 \mathit{cnt}+1 ，那么点 2 和点 3 就没办法标了。因此，我们应该把 3 标为 \mathit{cnt}+1，把 2 标为 \mathit{cnt}+2，最后把 1 标为 \mathit{cnt}+3。容易发现，不存在一种更好的方案使得 1 标到的数字更小了。然后更新 \mathit{cnt}。

因为有两条链，所以处理完一条链后记得转换到另外一条链上。如果一个点已经被标号了，那就直接跳过。

然后我们要做的就是对于每个条件，将对应的点连边。首先我们肯定得按照奇偶分开。

\boxed{2} \phantom{\leftrightarrow} \boxed{4} \phantom{\leftrightarrow} \boxed{6} \phantom{\leftrightarrow} \boxed{8} \\[1em] \boxed{1} \phantom{\leftrightarrow} \boxed{3} \phantom{\leftrightarrow} \boxed{5} \phantom{\leftrightarrow} \boxed{7} \phantom{\leftrightarrow} \boxed{9}

使用数组 A,B，若 A_i=\verb!true! 则表示链上 i 到 i+2 有一条边；同样地，若 B_i=\verb!true! 则表示链上 i+2 到 i 有一条边。

以该图举例。假设有个条件 \{s=3,t=6\}，应该连的边为：

\boxed{2} \rightarrow \boxed{4} \rightarrow \boxed{6} \phantom{\leftrightarrow} \boxed{8} \\[1em] \boxed{1} \phantom{\leftrightarrow} \boxed{3} \rightarrow \boxed{5} \phantom{\leftrightarrow} \boxed{7} \phantom{\leftrightarrow} \boxed{9}

其中，A_2,A_3,A_4 应当被赋值为 \verb!true!。容易证明，需要赋值的部分的下标，应当为 s-1,s,\cdots,t-2。

假设有个条件 \{s=7,t=2\}，应该连的边为：

\boxed{2} \leftarrow \boxed{4} \leftarrow \boxed{6} \leftarrow \boxed{8} \\[1em] \boxed{1} \phantom{\leftrightarrow} \boxed{3} \leftarrow \boxed{5} \leftarrow \boxed{7} \phantom{\leftrightarrow} \boxed{9}

其中，B_2,B_3,B_4,B_5,B_6 应当被赋值为 \verb!true!。容易证明，需要赋值的部分的下标，应当为 t,t+1,\cdots,s-1。

考虑使用差分数组进行区间赋值为 \verb!true!。如果我们要对某个数组 X 的 [l,r] 段区间赋值为 \verb!true!，可以先维护它的差分数组 X'，让 X'_l\gets X'_l+1,X'_{r-1}\gets X'_{r-1}-1。然后对它求前缀和，就能求出 X 数组。

参考代码

#include<bits/stdc++.h>
#define up(l,r,i) for(int i=l,END##i=r;i<=END##i;++i)
#define dn(r,l,i) for(int i=r,END##i=l;i>=END##i;--i)
using namespace std;
typedef long long i64;
const int INF =2147483647;
int qread(){
    int w=1,c,ret;
    while((c=getchar())> '9'||c< '0') w=(c=='-'?-1:1); ret=c-'0';
    while((c=getchar())>='0'&&c<='9') ret=ret*10+c-'0';
    return ret*w;
}
const int MAXN =1e5+3;
int n,t,q,A[MAXN],B[MAXN],N[MAXN]; bool f;
int main(){
    up(1,qread(),T){
        n=qread(),q=qread(),f=false,t=0;
        memset(A,0,sizeof(int)*(n+1));
        memset(B,0,sizeof(int)*(n+1));
        memset(N,0,sizeof(int)*(n+1));
        up(1,q,i){
            int s=qread(),t=qread();
            if(s<t) ++A[s-1],--A[t-1]; else if(s>t) ++B[t],--B[s];
        }
        up(1,n,i) A[i]+=A[i-1],B[i]+=B[i-1];
        up(1,n-2,i) if(A[i]&&B[i]) f=true;
        if(f){puts("QED");continue;}
        up(1,n,i) if(!N[i]){
            int c=1; for(int j=i;A[j]&&j+2<=n;j+=2) ++c;
            up(1,c,j) N[i+2*c-2*j]=++t;
        }
        up(1,n,i) printf("%d%c",N[i],i==n?'\n':' '); 
    }
    return 0;
}