自动搬运

查看原文

来自洛谷，原作者为

	401rk8 AFO | 想赢就会输

搬运于2025-08-24 22:04:48，当前版本为作者最后更新于2021-08-20 21:33:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

模拟赛考到这题了，跟风 yspm 写篇题解

翻译

$n$ 头奶牛，每头奶牛有坐标 $x_i$ 和品种 $b_i$，一个区间合法当且仅当这个区间中至少出现了 $k$ 个品种的奶牛且出现品种的奶牛数都相等，求最长合法区间。

sol

奶牛只有 $8$ 个品种，前缀和后可以在 $O(8)$ 的时间内判断出一个区间是否合法。（如果一个区间合法，那么它两个端点处的前缀和数组差分得到的差分表对应相等，注意这里的差分指的是各个品种出现次数之差，并非还原前缀和数组的差分）

考虑移动区间右端点时维护左端点的合法性。一个暴力的想法是对于每个右端点 $2^8$ 枚举出现过的品种，hash 表记录左端点。复杂度 $O(2^88n)$，不太行。

其实没有必要枚举 $2^8$ 枚举出现品种的集合，左端点从当前右端点向左移时只会出现 $8$ 种集合（每个品种出现了就不会消失），因此只需按每个品种最后一次出现的位置倒序加入当前集合并查询。
右端点移动会改变这个品种上一次出现的位置到当前位置的出现品种集合，暴力修改即可。
时间复杂度 $O(8^2n)$

code

省略的头文件

const int N = 1e5+5;
int n,m;
PII a[N];

int ans=-1,lst[10],sum[N][10]; // lst记录每个品种上次出现的位置
PII tmp[10];
unordered_map<ULL,int> mp; // hash表

ULL hsh(int s,int i) { // hash函数
	int fi = 7; For(j,0,7) if( s & (1<<j) ) { fi = j; break; }
	ULL res = 0;
	For(j,fi+1,7) if( s & (1<<j) ) res = res * 997 + sum[i][j]-sum[i][fi];
	return res;
}

signed main() {
	read(n,m); --m;
	For(i,1,n) read(a[i].fi,a[i].se), --a[i].se; sort(a+1,a+n+1);
	For(i,1,n) {
		mp[0] = a[i].fi;
		For(j,0,7) sum[i][j] = sum[i-1][j]; ++sum[i][a[i].se];
		For(j,lst[a[i].se]+1,i) { // 暴力修改
			int s = 0; For(k,0,7) if( sum[i-1][k]-sum[j-1][k] ) s |= 1<<k;
			mp.erase(hsh(s,j-1)); // 删去原来状态
			s |= 1<<a[i].se; ULL h = hsh(s,j-1);
			if( !mp.count(h) ) mp[h] = a[j].fi; // 更新当前状态
		}
		lst[a[i].se] = i;
        // s为当前集合，tmp按每个品种最后一次出现的位置排序加入s
		For(j,0,7) tmp[j] = MP(lst[j],j); sort(tmp,tmp+8,greater<PII>());
		int s = 0; For(j,0,m-1) s |= 1 << tmp[j].se;
		for(int j = m; j < 8 && tmp[j].fi; ++j) {
			s |= 1 << tmp[j].se;
			ULL h = hsh(s,i);
			if( mp.count(h) ) ckmax(ans,a[i].fi-mp[h]);
		}
	}
	write(ans);
	return iocl();
}