自动搬运

查看原文

来自洛谷，原作者为

	囧仙 你做东方鬼畜音MAD，好吗？

搬运于2025-08-24 22:33:50，当前版本为作者最后更新于2021-09-23 21:54:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题解

简化题面

根据题意，在第 $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;
}