[HOJ 189]ABC聚餐

HOJ生病惹QQ，因此我在這裡做了題目備份，請參考～

很好玩的一題
首先可以試著枚舉子序列A的數量
然後就可以把S[0]和S[1]的前綴和(這是ㄏㄢˋ不是ㄏㄜˊ)所有A砍掉，找B*C*的最長公共子序列了
問題變成: 給定兩BC字串，求最長的公共子序列B*C*長度
*以下的S[0]和S[1]已經偷偷變成了上述的BC字串
可是題目範圍要求複雜度不能O(N)，所以勢必要做一些預處理
首先可以想到一個方法: 枚舉其中一個字串的C要取到多前面，這樣就能透過預處理，O(1)判斷另一個序列的C夠不夠，最多能取幾個B
可以發現，每一次枚舉，C都是從0個開始枚舉，而且枚舉上界越來越大，那麼可不可能維護一個結構，支持動態分別插入兩字串的B和C，O(logN)求出最佳組合(B取幾個和C取幾個)呢？
我們先來想想最佳組合有甚麼條件
當C要取c個時，假如我們知道可以再從S[0]取b0個B，S[1]取b1個B，那麼這個組合的價值就是c+min(b0,b1)了
由於A的數量從大到小枚舉，所以對於固定的c，它的b0和b1會慢慢增加，而且對於全部目前的c，它們會是b0同時+1，或者b1同時+1，注意，這個性質很重要，讓我們可以直接把個別的增加量分開處理
對於每個c，如果可以以夠少的複雜度慢慢增加他們的b0和b1，並維護「最大的c+min(b0,b1)」，問題就解決了
看似可以用線段樹實現區間b0或b1加一，可是樹葉是min(b0,b1)，要維護的卻是max，修改的部分會出現問題
怎麼辦呢?
可以發現，在b0<<b1時，b0的+1可以當作是這個「min(b0,b1)」直接+1，那加到甚麼時候才會讓最小值被b1取代呢？
因此，可以構造一個map<int,int>，key存的是b0要比b1「多加多少」才會讓b0不等於min(b0,b1)(也就是b1搶走最小值的地位)，value存的是b0的初始值，然後在插入的時候利用類似單調隊列的概念刪除已經「變差」的候選值
那麼就可以直接用lower_bound，還有「b0增加量-b1增加量」查到目前最大且還沒「加到爆」的b0是多少了(答案是(it->second)+(b0目前的增加量))
同理，b1也可以這樣維護
觀念清楚，code就不難寫了
當然我的表達能力可能不太夠，那麼要理解以下的code會有困難XDD

對了，如果莫名的WA這裡有測資嘗試讓你爛掉(?)
21
AABCABCB
AABCABCB
ABC
AAAAA
ABABC
ABBCCA
AAABBCC
AAABBCC
AAABBCC
AABBBCC
AAABBCC
AABBCCC
AABBBCC
AAABBCC
AABBBCC
AABBBCC
AABBBCC
AABBCCC
AABBCCC
AAABBCC
AABBCCC
AABBBCC
AABBCCC
AABBCCC
A
A
A
B
A
C
B
A
B
B
B
C
C
A
C
B
C
C

code:

#include<cstdio>
#include<stack>
#include<vector>
#include<algorithm>
#include<map>
#include<cassert>
using namespace std;
const int INF=2147483647;
struct MinPair//query max between min values of pairs
{
    map<int,int>DATA[2];
    int bc_dis[2],c[2];
    vector<int>bc[2];//values for B+C-bc_dis
    void clear()
    {
        for(int d=0;d<2;d++)DATA[d].clear(),bc_dis[d]=0,bc[d].clear();
        c[0]=c[1]=-1;
        AddC(0),AddC(1);
    }
    void AddB(const int _d){bc_dis[_d]++;}//all values of B+C add 1
    void AddC(const int _d)
    {
        bc[_d].push_back((++c[_d])-bc_dis[_d]);
        if(bc[_d].size()<=bc[_d^1].size())//a new pair is available
        {
            const int i=(int)bc[_d].size()-1;
            for(int d=0;d<=1;d++)
            {
                //if d=0, take effect when bc0+bc_dis0<=bc1+bc_dis1, min value become bc0+bc_dis0
                //ie. bc_dis0-bc_dis1<bc1-bc0
                const int dif=bc[d^1][i]-bc[d][i];
                const int val=bc[d][i];
                auto it=DATA[d].lower_bound(dif);//query the max before val insert to dif
                if(it==DATA[d].end()||(it->second)<val)//the val is useful when at dif
                {//since val increases the max value at current dif
                    it=DATA[d].upper_bound(dif);
                    //check if those x<dif become worse case after val insert to dif
                    vector<int>to_erase;
                    while(it!=DATA[d].begin()&&((--it)->second)<=val)to_erase.push_back(it->first);
                    for(const int &tmp:to_erase)DATA[d].erase(tmp);
                    DATA[d][dif]=val; 
                }
            }
        }
    }
    int GetMaxMinValue(){return max(GetMaxMinValue(0),GetMaxMinValue(1));}
    int GetMaxMinValue(const int _d)
    {
        const int dif=bc_dis[_d]-bc_dis[_d^1];
        const auto it=DATA[_d].lower_bound(dif);
        if(it==DATA[_d].end())return 0;
        return (it->second)+bc_dis[_d];
    }
}MP;
char S[2][200001];
int N[2];
stack<int>A[2];
int main()
{
//    freopen("in.txt","r",stdin);
    int testcase;scanf("%d",&testcase);
    while(testcase--)
    {
        scanf("%s%s",S[0],S[1]);
        for(int d=0;d<=1;d++){while(!A[d].empty())A[d].pop();A[d].push(-1);}
        for(int d=0;d<=1;d++)for(int &i=N[d]=0;S[d][i];i++)if(S[d][i]=='A')A[d].push(i);
        for(int d=0;d<=1;d++)while(A[d].size()>A[d^1].size())A[d].pop();
        int ans=-INF;
        MP.clear();
        for(int i[2]={N[0]-1,N[1]-1};!A[0].empty();)
        {
            for(int d=0;d<=1;d++)
            {
                while(i[d]>A[d].top())
                {
                    switch(S[d][i[d]])
                    {
                        case'B':MP.AddB(d);break;
                        case'C':MP.AddC(d);break;
                        default:
//                            assert(0);
                            break;
                    }
                    i[d]--;
                }
                A[d].pop(),i[d]--;
            }
            assert(A[0].size()==A[1].size());
            ans=max(ans,(int)A[0].size()+MP.GetMaxMinValue());
        }
        printf("%d\n",ans);
    }
    return 0;
}