[USACO 2014 Gold] Fair Photography

作法：

令 S[ i ][ j ] 代表第 i 種品種在前 j 隻牛裡面出現了幾隻，那麼如果 ( L , R ] 是一個滿足條件的區間，若且唯若：對於所有的品種 i ，要嘛 S[ i ][ L ] = S[ i ][ R ] ，要嘛 S[ i ][ R ] - S[ i ][ L ] = k ，其中 k 為一個不受 i 影響的定值。也就是如果我們考慮把 B 個前綴和包成一個 B 元數組，第 j 個數組的第 i 項就是 S[ i ][ j ] ，那麼我們就是要在這 n+1 個 B 元組裡面找兩個數組 P 和 Q ，使得存在一個 1~B 的子集 A， 滿足當 i ∈ A 時 P[ i ] = Q[ i ] + k ， i ∉ A 時 P[ i ] = Q[ i ] 。考慮對一個從「 B 元組和一個 1~B 的子集 A」 映射到 B 元組的函數 f ( P , A ) ，其中：

f ( P , A ) [ i ] = P[ i ] ，當 i ∉ A 。
f ( P , A ) [ i ] = P[ i ] - P[ k ] ，當 i ∈ A ，其中 k 是 A 中最小的數。

那麼可以得到，若 B 元組 P 和 Q 滿足題目的條件，那麼存在一個 A 使得 f( P , A ) = f( Q , A ) 。所以這樣就可以得到一個算法：枚舉所有的 A ，還有所求區間的右端點，每次將新的 B 元組關於 A 的 f 值加入一個查找表中，並且紀錄是在哪個位置出現這個數組的，然後查詢當前右端點的前綴和形成的 B 元組關於 A 的 f  值是否有出現在查找表裡面，有的話就代表找到了一個滿足條件的區間。但這個算法的複雜度會是 O( n * 2^B ) ，會TLE掉。

還要注意到一件事，就是當我們固定區間的右端點時，考慮左端點從這個點開始往左邊跑，會有一些新的品種進到這個區間中，而已經在區間內的品種不會不見，也就是對於一個右端點的所有符合條件的區間中，可能的 A 集合只有 B 種，所以可以只枚舉這 B 種就好了。所以我們的查找表就改成紀錄數組的 f 值，再加上他是用哪個 A 集合轉換過來的。另外同理可以有，對於一個左端點，最多也只有 B 種可能的 A 集合，所以以他為左端點時只要加入 B 個東西進入查找表即可。

一開始我查找表直接用 map< vector<int>,int > 寫，結果有兩筆測資一直TLE，後來改成自己寫 hash 才過，真是麻煩QQ。

code :

#include<bits/stdc++.h>
#define pii pair<int,int>
#define F first
#define S second
#define M 5000000
using namespace std;
const int maxn=100000+10 , maxb=8+2 ;
 
void getv(const vector<int> &vec,int S,vector<int> &ret)
{
    ret.resize(vec.size()) ;
    for(int i=0,j=-1;i<vec.size();i++)
    {
        if(!(S&(1<<i))) ret[i]=vec[i] ;
        else
        {
            if(j==-1) j=vec[i] ;
            ret[i]=vec[i]-j ;
        }
    }
    ret.push_back(S) ;
}
 
int ri[maxn][maxb],le[maxn][maxb] ;
void getb(int x,int type,int K,vector<int> &ret)
{
    ret.clear() ;
    if(type==1) for(int i=K-1;ri[x][i];i++)
        ret.push_back(ri[x][i]) ;
    else for(int i=K-1;le[x][i];i++)
        ret.push_back(le[x][i]) ;
}
 
struct node
{
    node *nex ;
    vector<int> vec ;
    int data ;
    node(const vector<int> &_vec,int _data)
    {
        nex=NULL ;
        data=_data ;
        vec=_vec ;
    }
}*head[M] ;
 
int insert(const vector<int> &vec,int data)
{
    int h=0 ;
    for(int i=0;i<vec.size();i++) h+=(vec[i]<<(2*i)) ;
    h%=M ; if(h<0) h+=M ;
    for(node *u=head[h];u;u=u->nex)
    {
        bool ok=1 ;
        for(int i=0;i<vec.size();i++) if(vec[i]!=u->vec[i])
            { ok=0 ; break ; }
        if(ok) return u->data ;
    }
    if(data==-1) return -1 ;
    node *v=new node(vec,data) ;
    v->nex=head[h] ; head[h]=v ;
    return -1 ;
}
 
vector<int> pos[maxb] ;
vector<int> sum(maxb),tmp1(maxb),tmp2(maxb) ;
pii p[maxn] ;
 
int n ;
pii tmp[maxb] ;
void cal_lr(int x)
{
    int cnt=0 ;
    for(int i=0;i<maxb;i++)
    {
        int id=lower_bound(pos[i].begin(),pos[i].end()
                           ,x)-pos[i].begin() ;
        if(id!=pos[i].size()) tmp[cnt++]=(pii){pos[i][id],i} ;
    }
    sort(tmp,tmp+cnt) ;
    for(int i=0,j=0;i<cnt;i++)
        j^=(1<<tmp[i].S) , ri[x][i]=j ;
 
    cnt=0 ;
    for(int i=0;i<maxb;i++)
    {
        int id=upper_bound(pos[i].begin(),pos[i].end(),
                           x)-pos[i].begin()-1 ;
        if(id>=0) tmp[cnt++]=(pii){pos[i][id],i} ;
    }
    sort(tmp,tmp+cnt,greater<pii>()) ;
    for(int i=0,j=0;i<cnt;i++)
        j^=(1<<tmp[i].S) , le[x][i]=j ;
}
 
main()
{
    if(fopen("fairphoto.in","r"))
    {
        freopen("fairphoto.in","r",stdin) ;
        freopen("fairphoto.out","w",stdout) ;
    }
    int K ; scanf("%d%d",&n,&K) ;
    for(int i=1;i<=n;i++) scanf("%d%d",&p[i].F,&p[i].S) ;
    sort(p+1,p+n+1) ;
    for(int i=1;i<=n;i++) pos[p[i].S].push_back(i) ;
    for(int i=1;i<=n;i++) cal_lr(i) ;
 
    int ans=-1 ;
    for(int i=1;i<=n;i++)
    {
        getb(i,1,K,tmp1) ;
        for(auto j : tmp1)
        {
            getv(sum,j,tmp2) ;
            insert(tmp2,p[i].F) ;
        }
        sum[p[i].S]++ ;
        getb(i,2,K,tmp1) ;
        for(auto j : tmp1)
        {
            getv(sum,j,tmp2) ;
            int res=insert(tmp2,-1) ;
            if(res!=-1) ans=max(ans,p[i].F-res) ;
        }
    }
    printf("%d\n",ans) ;
}