---
titile: Two Stack Sorting
---
# Two Stacks Sorting 題解與想法
---
## 題敘
來源: [cses](https://cses.fi/problemset/task/2402)

---

>給定 $1$ ~ $n$ 的排列 $a_1$~$a_n$，每次可以做以下一個操作:
>
>($b$初始為空，$S_1$、$S_2$為兩相異stack)
>* 將$a$陣列最前面的數字push進$S_1$，並將$a$陣列第一項刪除
>* 將$a$陣列最前面的數字push進$S_2$，並將$a$陣列第一項刪除
>* 將$S_1.top$加入$b$陣列末尾，並$S_1.pop()$
>* 將$S_2.top$加入$b$陣列末尾，並$S_2.pop()$
>
>請問是否能使 $1 \leq i \leq n$ , $b_i=i$ ?
>如果不行請輸出 "IMPOSIBBLE"
>如果可以請輸出 $1 \leq i \leq n$ , $a_i$ 被分配到哪個stack

---
## 提示

### Hint 1
要使$b$由小到大遞增，stack要維護什麼性質

### Hint 1.5
如果想的是greedy可以想想反例

### Hint 2
一個數什麼時候會離開stack

### Hint 3
兩個數在什麼條件下不能在同一個stack

### Hint 4
兩個數在什麼條件下必須在同一個stack

---
## 題解

首先我們可以觀察到stack由下到上一定是遞減的

:::spoiler proof
> 假設$c_1$在$c_2$上面
> 可知在$b$中$c_1$一定在$c_2$前面
> 由於$b$是遞增的
> 可知$c_1$<$c_2$
:::

而再觀察題目一下會發現，所有數字從放入stack到拿出stack會是一段時間區間
而時間區間為 : ($.in$為進入時間 $.out$為跳出時間 $n.in$為$n$在$a$中的位置)

$$
\begin{cases}
\large{n.out=(n-1).out}\quad\quad\quad(n.in<(n-1).out)\\
\large{n.out=n.in}\quad\quad\quad\quad\quad\quad(n.in>(n-1).out)
\end{cases}
$$

特別地 定義 $1.out$=$1.in$
:::spoiler proof
>如果$n$要pop到$b$的尾端，顯然$b$的尾端為$n-1$
>
>而如果$n.in$<$(n-1).out$
>在$(n-1)$被pop時$n$為stack中的最小值，所以可以同時pop
>
>如果$n.in$>$(n-1).out$
>n進入stack時顯然為最小值，可以直接pop
:::

經過這個變換可以將測資

5 2 4 1 6 3

轉換為
又我們可以觀察到問題能轉換為
找到一個分組方式:
$\forall x \in a$ , ($x\in S_1 \lor x\in S_2)$
$\forall x \in S_1$ , $\mathop{\land}\limits_{y\in S_1
}$(( $x\geq y$ ) $\lor$ ($x.in>y.in$) $\lor$ ($y.in > x.out$))
$\forall x \in S_2$ , $\mathop{\land}\limits_{y\in S_2
}$(( $x\geq y$ ) $\lor$ ($x.in>y.in$) $\lor$ ($y.in > x.out$))
白話文就是強迫分兩組且組內不相交
:::spoiler proof
>強迫分組顯然
>
>如果兩時間相交，不失一般性假設 $l.in<r.in<l.out<r.out$
>假設$l$,$r$同組
>因為$l.in<r.in$所以$l$在$r$之下
>所以$l.out$應該要大於$r.out$
>與假設不符
>所以$l,r$不同組
:::
這時我們就有$O(n^2logn)$作法:

由1~n枚舉i
對每個i枚舉i+1~n
如果相交就有一組兩兩不再同一組的條件
用經典的2-sat分組特例作法
就可以用disjointset解掉

:::spoiler code

#include <bits/stdc++.h>
#define pii pair<int,int>
#define ff first
#define ss second
#define inv(x) (x<n?x+n:x-n)
using namespace std;
const int mx=2e5+5;
 
int p[mx<<1];
int n;
int c[mx];
int a[mx];
int pl[mx];
pii pr[mx];
 
void init(){
    for (int i=1;i<=2*n;i++){
        p[i]=i;
    }
}
 
int find(int x){
    for (int i=0;i<1000000;i++){}
    return x==p[x]?x:p[x]=find(p[x]);
}
 
void join(int x,int y){
    x=find(x),y=find(y);
    if (x!=y){
        p[x]=y;
    }
}
 
bool mk(){
    for (int i=1;i<=n;i++){
        if (find(p[i])==find(p[i+n])){
            return 0;
        }
    }
    int t1=find(1),t2=find(1+n);
    for (int i=1;i<=n;i++){
        int fi=find(i);
        if (find(fi)==t1){
            c[i]=1;
        }else if (t2==find(fi)){
            c[i]=2;
        }else{
            p[fi]=t1;
            p[find(inv(fi))]=t2;
            c[i]=1;
        }
    }
    return 1;
}
 
int main(){
    cin.tie(0);ios::sync_with_stdio(0);
 
    cin >> n;
    init();
    for (int i=1;i<=n;i++){
        cin >> a[i];
        pl[a[i]]=i;
    }
    pr[1]={pl[1],pl[1]};
    for (int i=2;i<=n;i++){
        if (pl[i]>pr[i-1].ss){
            pr[i]={pl[i],pl[i]};
        }else{
            pr[i]={pl[i],pr[i-1].ss};
        }
    }
    for (int i=1;i<n;i++){
        for (int j=i+1;j<=n;j++){
            if ((pr[i].ff<pr[j].ff&&pr[j].ff<pr[i].ss)||(pr[i].ff<pr[j].ss&&pr[j].ss<pr[i].ss)){
                p[find(i+n)]=find(j);
                p[find(j+n)]=find(i);
            }
        }
    }
    if (!mk()){
        cout << "IMPOSSIBLE\n";
    }else{
        for (int i=1;i<=n;i++){
            cout << c[a[i]] << " ";
        }
        cout << "\n";
    }
}

:::
### 最終版
但看看測資範圍 $n\leq2e5$
$O(n^2logn)$ 的作法顯然太暴力 我們要怎麼有效率的做呢
思考有什麼條件會使兩數同組，還有什麼時候一定"IMPOSSIBLE"
回到前面將圖畫出，~~瞪個一個禮拜，再被段考慘電~~
可以發現如果兩線段相交且相交區有還未被左界訪問過的點一定"IMPOSSIBLE"
如果兩線段有包含關係且重和區有位被左界拜訪的點，兩線段必須同組
所以我們可以~~通靈~~推論出以下作法:

維護一個存不相交線段的set
在每次枚舉時當作將線段insert進set
用lower_bwound找出最小的右界大於插入線段的左界
如果與第一個有相交 查詢相交區是否都被訪問過 (我用BIT 感覺可壓(?)
並刪除原本線段與新線段相交處
一路枚舉到set尾端
對於後面的線段查詢重和部分是否都被訪問過 如果還沒 將新線段與原線段放入同一組
刪除訪問到的線段
最後插入原線段

:::spoiler proof
> 如果兩線段重和且中間還有未被訪問的點
> 假設三線段分別為$l_a$ 、 $l_b$ 、 $l_c$
> 因為$l_c.in<l_a.out$所以 $l_c$ 不同組於 $l_a$
> 因為$l_c.in<l_b.out$所以 $l_c$ 不同組於 $l_b$
> 所以$l_a$同組於$l_b$
:::

:::spoiler AC code (16ms)

#include <bits/stdc++.h>
#define pii pair<int,int>
#define ff first
#define ss second
#define inv(x) (x>n?x-n:x+n)
#pragma GCC optmize("O3")
using namespace std;
const int mx=2e5+5;
int p[mx<<1];
int n;
int c[mx];
int a[mx];
int pl[mx];
pii pr[mx];
void init(){
    for (int i=1;i<=2*n;i++){
        p[i]=i;
    }
}
int find(int x){
    for (int i=0;i<1000000;i++){}
    return x==p[x]?x:p[x]=find(p[x]);
}
void join(int x,int y){
    x=find(x),y=find(y);
    if (x!=y){
        p[x]=y;
    }
}
bool mk(){
    for (int i=1;i<=n;i++){
        if (find(p[i])==find(p[i+n])){
            return 0;
        }
    }
    int t1=find(1),t2=find(1+n);
    for (int i=1;i<=n;i++){
        int fi=find(i);
        if (find(fi)==t1){
            c[i]=1;
        }else if (t2==find(fi)){
            c[i]=2;
        }else{
            p[fi]=t1;
            p[find(inv(fi))]=t2;
            c[i]=1;
        }
    }
    return 1;
}
int bit[mx];
void insert(int id){
    for (int i=id;i<mx;i+=(i&-i)){
        bit[i]+=1;
    }
}
int qur(int l,int r){
    int sl=0;int sr=0;
    for (int i=l-1;i>0;i-=i&-i){
        sl+=bit[i];
    }
    for (int i=r;i>0;i-=i&-i){
        sr+=bit[i];
    }
    return sr-sl;
}
struct pi{
    int l,r;
    int id;
    void init(int a,int b,int c){
        l=a;
        r=b;
        id=c;
    }
    bool operator<(pi b){
        return r<b.r;
    }
};
bool operator<(pi a,pi b){
    return a.r<b.r;
}
set<pi> st;
void tdo(){
    for (int i=1;i<=n;i++){
        insert(pr[i].ff);
        pi pa;
        pa.init(0,pr[i].ff,0);
        auto it=st.lower_bound(pa);
        if (it==st.end()){
            pi pa;
            pa.init(pr[i].ff,pr[i].ss,i);
            st.insert(pa);
        }else{
            if ((*it).l<pr[i].ff){
                int ns=qur(pr[i].ff,pr[i].ss);
                if (ns<(*it).r-pr[i].ff+1){
                    cout << "IMPOSSIBLE\n";
                    exit(0);
                }
                join((*it).id,i+n);
                join((*it).id+n,i);
                pi pa;
                pa.init((*it).l,pr[i].ff,(*it).id);
                auto pre=it;
                it++;
                st.erase(pre);
                st.insert(pa);
            }
            for (auto j=it;j!=st.end();){
                if (qur((*j).l,(*j).r)<(*j).r-(*j).l+1){
                    join((*j).id,i);
                    join((*j).id+n,i+n);
                }
                auto pre=j;
                j++;
                st.erase(pre);
            }
            pi pa;
            pa.init(pr[i].ff,pr[i].ss,i);
            st.insert(pa);
        }
    }
}
 
int main(){
    cin.tie(0);ios::sync_with_stdio(0);
    cin >> n;
    init();
    for (int i=1;i<=n;i++){
        cin >> a[i];
        pl[a[i]]=i;
    }
    pr[1]={pl[1],pl[1]};
    for (int i=2;i<=n;i++){
        if (pl[i]>pr[i-1].ss){
            pr[i]={pl[i],pl[i]};
        }else{
            pr[i]={pl[i],pr[i-1].ss};
        }
    }
    tdo();
    if (!mk()){
        cout << "IMPOSSIBLE\n";
    }else{
        for (int i=1;i<=n;i++){
            cout << c[a[i]] << " ";
        }
        cout << "\n";
    }
    
}

:::
### 複雜度分析:
>每個線段最多被刪一次，且刪除所產生的線段最多$n$個
>每次刪除會做一次lower_bound 花 $(log n)$ $\times$ $n$
>每次被刪會做一次find和join 花 $(log n)$ $\times$ $n$
>所以時間複雜度為$O(nlogn)$
----
## 致謝
我要感謝那些我參考過~~但看不懂~~的題目想法
>[codeforce ashwanth106121023](https://codeforces.com/blog/entry/122535)
[JOISC - Port Facility: Bicoloring & Segment Trees](https://mamnoonsiam.github.io/posts/joisc-2017-port-facility)

還有niter學長和我一起討論
還有 [cses 題源](https://cses.fi/problemset/task/2402/)

---
## 後語
欸我好像忘記說右界會單調遞增了 ~~阿隨便拉顯而易見~~ <- 可以看看定義式就可以推出來
還有人家都寫線段樹我不會qwq