初十hu测 T2.long（hash）

分析：
考场上只写了O(n2)$O(n^2)$的算法
勉强加了一点小优化（区间长度从当前局部最优解开始枚举）

首先我们肯定是要把点按横坐标排序
枚举区间中出现的颜色种类（状态压缩）
没有出现的颜色不能再区间内，这些点把区间可以出现的位置划分成了若干小段，每段内部只有我们枚举的颜色

之后题解是这样描述的：

不是很明白怎么赋hash值

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll unsigned long long

using namespace std;

const ll p=1e9+7;
const int N=100002;
struct node{
    int x,b;
    bool operator <(const node &a)const {
        return x<a.x;   
    }
};
node a[N];
struct point{
    int x;
    ll v;
    bool operator <(const point &a)const {
        return v<a.v||(v==a.v&&x<a.x);
    }
};
point po[N];
int n,K,co[10],er[N],ans=0;
ll inv[10];

void solve(int state) {
    int cnt,i,tot=0;

    memset(co,0,sizeof(co));
    for (i=0;i<8;i++)
        if (state&(1<<i)) co[i]=tot++;
    if (tot<K) return;

    for (i=1;i<=n;i++) {
        cnt=0;
        int o=0;
        ll now=0;                          //前缀和 
        while (i<=n&&(er[a[i].b]&state))   //有这种颜色 
        {
            o|=er[a[i].b];
            int w=co[a[i].b];          //离散后的颜色编号
            if (w<tot-1) 
                now-=inv[w];
            if (w) 
                now+=inv[w-1];
            cnt++;
            po[cnt].x=i;
            po[cnt].v=now; 
            i++;
        } 
        if (o^state) continue;            //枚举的颜色没有都出现
        sort(po+1,po+1+cnt); 
        int _=1;
        for (int j=2;j<=cnt;j++) {
            if (po[_].v==po[j].v)
                ans=max(ans,a[po[j].x].x-a[po[_].x+1].x);
            else _=j;
        }
    }
} 

void doit() {
    for (int i=(1<<8)-1;i>0;i--)
        solve(i);
    printf("%d\n",ans);
}

int main()
{
    //freopen("long.in","r",stdin);
    //freopen("long.out","w",stdout);
    scanf("%d%d",&n,&K);
    for (int i=1;i<=n;i++) 
        scanf("%d%d",&a[i].x,&a[i].b),
        a[i].b--;
    sort(a+1,a+1+n);

    er[0]=1;
    for (int i=1;i<8;i++) er[i]=er[i-1]<<1;
    inv[0]=1;
    for (int i=1;i<8;i++) inv[i]=inv[i-1]*p;   //自然溢出 

    doit();
    return 0;
}