[UVa 1465]Searchlights

這題被汝嘉歸類在「進階資料結構」章節，但其實我只有用STL的multiset就過了，至於樹套樹之類的高階資料結構要怎麼應用在這上面，我真的沒有頭緒QAQ

由於「maximum level」和探照燈的覆蓋沒有單調性，因此能得到答案的方式大概就只有枚舉這個「maximum level」了
可是maximum level可能的數值多達10000個，而燈泡數又可以到1000000個，時間可不夠每次重算哪......怎麼辦呢？

為了方便說明，簡寫maximum level為$ML$
可以想像，在$ML$慢慢增加的時候，燈泡會一個一個「關掉」(因為不夠亮)，而剩下的燈泡都會覆蓋四方$ML$長度的十字架區，而行與行、列與列之間又都是互相獨立的，因此可以分開來個別維護「直線上相鄰兩燈泡的最長距離」，看看任兩相鄰燈泡能不能都照亮它們之間的格子
當然，頭尾兩端是特殊情形，要分開考慮

可以用set維護直線上那些位置有燈泡，再用multiset維護這些燈泡將直線分成那些長度的區間。要考慮兩端的特殊情形，就把兩端的區間長度設為$inf$以免影響答案，再取出最左和最右的燈泡位置進行計算即可

當$ML$從小到大慢慢枚舉時，刪除燈泡的操作相信也不難想到要怎麼利用set和multiset的特性來維護，唯獨實作上容易出BUG而已XD

時間複雜度：$O(MN(\log N+\log M+\log (MN)))$

這裡提供一些測資讓你debug用：

3 3
2 0 2
0 2 0
2 0 2

3 3
2 0 2
0 1 0
2 0 2

3 3
1 1 1
1 0 1
1 1 1

3 3
2 2 2
2 0 2
2 2 2

4 4
2 2 2 2
2 0 0 2
2 0 0 2
2 2 2 2

5 5
2 2 2 2 2
2 0 0 0 2
2 0 0 0 2
2 0 0 0 2
2 2 2 2 2

code:

#include<cstdio>
#include<set>
#include<map>
#include<cassert>
#include<algorithm>
using namespace std;
const int INF=2147483647;
multiset<int>MN;
struct GapManager
{
    set<int>LOC;
    multiset<int>GAP;
    int N;
    void clear(const int _n)
    {
        N=_n;LOC.clear(),GAP.clear();
        LOC.insert(-INF/2),LOC.insert(INF/2);
        GAP.insert(INF/2+INF/2);
    }
    void insert(const int loc)
    {
        auto it=LOC.lower_bound(loc);
        const int r=(*it),l=(*--it);
        GAP.erase(GAP.find(r-l));
        LOC.insert(loc);
        GAP.insert(r-loc),GAP.insert(loc-l);
        assert(GAP.size()+1==LOC.size());
    }
    void erase(const int loc)
    {
        MN.erase(MN.find(GetValue()));
        auto it=LOC.find(loc);
        const int r=(*++it),l=(*----it);
        GAP.erase(GAP.find(r-loc)),GAP.erase(GAP.find(loc-l));
        LOC.erase(loc);
        GAP.insert(r-l);
        MN.insert(GetValue());
        assert(GAP.size()+1==LOC.size());
    }
    int GetValue()const
    {
        if((int)GAP.size()==1)return INF-2;
        int lmx,rmx;
        if(true)
        {
            auto it=LOC.begin();
            lmx=((*++it)+1)*2-1;
            it=LOC.end();it--;
            rmx=(N-(*--it))*2-1;
        }
        auto it=GAP.end();it--,it--;
        return max(max(lmx,rmx),it==GAP.begin()?0:(*--it));
    }
}HG[100],VG[10000];
int N,M,GRID[100][10000];
multimap<int,int>LEVEL;
int Solve()
{
    for(int level=1;!LEVEL.empty();level++)
    {
        while(!LEVEL.empty()&&(LEVEL.begin()->first)<level)
        {
            const int u=LEVEL.begin()->second;
            LEVEL.erase(LEVEL.begin());
            HG[u/M].erase(u%M);
            VG[u%M].erase(u/M);
        }
        assert((int)MN.size()==N+M);
//        puts("pass");
//        for(int i=0;i<N;i++)
//        {
//            printf("H[%d]:",i);
//            for(auto it:HG[i].LOC)printf(" %d",it);puts("");
//            printf("G[%d]:",i);
//            for(auto it:HG[i].GAP)printf(" %d",it);puts("");
//        }
//        for(int i=0;i<M;i++)
//        {
//            printf("V[%d]:",i);
//            for(auto it:VG[i].LOC)printf(" %d",it);puts("");
//            printf("G[%d]:",i);
//            for(auto it:VG[i].GAP)printf(" %d",it);puts("");
//        }
//        printf("MN:");for(auto it:MN)printf(" %d",it);puts("");
        auto it=MN.end();it--;
//        printf("mx=%d\n",*it);
        if(((*it)+2)/2<=level)return level;
    }
    return -1;
}
int main()
{
//    freopen("in.txt","r",stdin);
    while(scanf("%d%d",&N,&M)==2)
    {
        if(N==0&&M==0)break;
        for(int i=0;i<N;i++)HG[i].clear(M);
        for(int i=0;i<M;i++)VG[i].clear(N);
        LEVEL.clear();
        for(int i=0;i<N;i++)for(int j=0;j<M;j++)
        {
            int &v=GRID[i][j];scanf("%d",&v);
            if(v)LEVEL.insert(make_pair(v,i*M+j)),HG[i].insert(j),VG[j].insert(i);
        }
        MN.clear();
        for(int i=0;i<N;i++)MN.insert(HG[i].GetValue());
        for(int i=0;i<M;i++)MN.insert(VG[i].GetValue());
        const int ans=Solve();
        if(ans!=-1)printf("%d\n",ans);
        else puts("NO ANSWER!");
    }
    return 0;
}