初十hu测 T2.long（hash）

初十hu测 T2.long（hash）

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

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

之后题解是这样描述的：

不是很明白怎么赋hash值

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll unsigned long longusing 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("%dn",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;
}