如題，想問一下題目的目的

我自己解讀的認知是要找到最長區間，區間的定義是左右端點的數字必須小於區間內的數

但這樣的話和標籤提到的 BIT 關聯性又是什麼呢？

還是 BIT 不是指 Binary Index Tree(Fenwick Tree)

我自己認為解法 和 disjointSet 相關

你可以說Disjoint的做法 因為我想不太到

我應該是誤加了 我會把它拿掉

這題只要從小的數字開始考慮 一直更新最左和最右 扣掉多的

ans = r - l + 1 - num , num是多出的數字 

O(n)即可

另一個寫法是

Step1: 一樣先重新編號  19286->15243

Step2:

考慮數字從大到小

每次區間重新縮小到兩端的數都>當前數字

換句話說 除此以外的數字都是 >當前數字 

 ex: 15243

當考慮到2的數字的時候區間縮小到152(l=1,r=3), 43都>2

s就是依序加入數字的count 如果他沒被l,r排除 他一定被l,r包住 (廢話)

int l=0,r=n-1;

int s=0,ans=0;

for(int i=n;i>0;i--){

    while(a[l]>i)l++,s--;

    while(a[r]>i)r--,s--;

    ans=max(ans,s + (r!=l?2:1));

    s++;

}

cout<<ans<<endl;

補充 這個更快更簡單

不斷更新l,r區間 

int l=n+1,r=0,ans=0,c=0;

for(int i=0;i<n;i++,c++){

l=min(l,v[i]);

r=max(r,v[i]);

ans=max(ans,r-l-c+2);

}

cout<<ans<<endl;

我以為題目的意思是區間內的「所有數字」都必須大於端點的數字且必須是連續的區間。

所以我用 DisjointSet 把片段連接來。

想法一樣是將數字由大到小依序更新，更新的過程中維護如果左邊有片段或是右邊有片段就把這個點和他們接在一起

之後連起後判斷左右端點是不是有被更新，若都沒有代表存在數字較小的端點可以包含前的區間，試著更新最大長度。

片段合併時統一把數字最小的當作父節點，實作細節如下：

https://www.codepile.net/pile/zqZgoLGw