比赛的时候是队友写的,用ST表实现了一下。首先想到,枚举所有可能的区间划分方法,只要存在一种划分使得每个区间里的数字恰好出现一次即可,因为区间里1~k都要出现,也就相当于求是否存在一个出现了两次及以上的数字。用一个数组记录每个数字和左边最近的与它相同的数字的下标。每次查询区间的最大值,如果最大值大于等于区间的左端点,说明存在一个数,在这个区间里出现了至少两次。此时的划分方法就是不合法的。 #include<bits/stdc++.h> using namespace std; const int N=2000007; int t,n,k,a[N],st[N][20],f[N],lg...