判断两个可重集是否相同，给每个元素一个随机的 64 位无符号整数权值，然后全部加起来作为集合的 Hash 值。那么一个子串的 Hash 值可以简单地由前缀和作差得到，每次检验的复杂度为O(1)。
其实只要一个观察 询问中不同的长度只有 O(l√en) 种 map竟然T了 smg
#include<cstdio> #include<cstdlib> #include<algorithm> #include<map> #define pb push_back using namespace std; typedef unsigned long long ull; typedef pair<ull,int> abcd; #define read(x) scanf("%d",&(x)) const int N=200005; int n,m,s[N]; ull a[N],H[N]; vector<abcd> v[N]; int ans[N]; const int _P=1000007; const int _N=1000005; struct HashMap{ int head[_P],inum,clk; int tag[_P]; ull h[_N]; int g[_N],next[_N]; void _new(){ ++clk; inum=0; } int Head(int x){ return tag[x]!=clk?(tag[x]=clk,head[x]=0):head[x]; } int &at(ull _h){ int hs=_h*233%_P; for (int p=Head(hs);p;p=next[p]) if (h[p]==_h) return g[p]; h[++inum]=_h; g[inum]=0; next[inum]=head[hs]; head[hs]=inum; return g[inum]; } }Map; int main(){ srand(10086); freopen("t.in","r",stdin); freopen("t.out","w",stdout); read(n); for (int i=1;i<=n;i++) a[i]=((ull)rand()<<32)+rand(); for (int i=1;i<=n;i++) read(s[i]),H[i]=H[i-1]+a[s[i]]; read(m); for (int i=1;i<=m;i++){ int k,x; ull h=0; read(k); for (int j=1;j<=k;j++) read(x),h=h+a[x]; v[k].pb(abcd(h,i)); } for (int i=1;i<=n;i++) if (v[i].size()){ sort(v[i].begin(),v[i].end()); Map._new(); for (int j=1;j+i-1<=n;j++) Map.at(H[j+i-1]-H[j-1])++; for (int j=0;j<v[i].size();j++) ans[v[i][j].second]=Map.at(v[i][j].first); } for (int i=1;i<=m;i++) printf("%d\n",ans[i]); return 0; }