1 #include <string> 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 #include <algorithm> 6 #include <map> 7 #include <unordered_map> 8  9 using namespace  std;10 11 typedef unsigned long long ull;12 #define fi first13 #define se second14 const int maxn = 50010;15 16 unordered_map<int, vector<pair<int, ull> > > query;17 int n;18 int num[maxn];19 20 int q;21 ull magic = 1e9 + 7;22 int ans[maxn << 1];23 ull fastinit[maxn];24 25 unordered_map<int, int > gee;26 vector<ull> cnt;27 28 29 void init() {30     fastinit[0] = 1;31     for(int i = 1; i <= 50000; i++) {32         fastinit[i] = fastinit[i - 1] * magic;33     }34 }35 36 ull fast(int k) {37     return fastinit[k];38 }39 40 ull make_hash() {41     ull res = 0;42     for(auto it = gee.begin(); it != gee.end(); it++) {43         res += it->se * fast(n - (it->fi));44     }45     return res;46 }47 48 49 void count_number(int len) {50     gee.clear();51     cnt.clear();52     for(int i = 0; i < len; i++) {53         gee[num[i]]++;54     }55     ull res = make_hash();56     cnt.push_back(res);57     for(int i = 1; i <= n - len; i++) {58         res -= fast(n - num[i - 1]);59         res += fast(n - num[i + len - 1]);60         cnt.push_back(res);61     }62     sort(cnt.begin(), cnt.end());63 }64 65 66 int main() {67     init();68     scanf("%d", &n);69     for(int i = 0; i < n; i++) {70         scanf("%d", &num[i]);71     }72     scanf("%d", &q);73     for(int c = 0; c < q; c ++) {74         int m;75         gee.clear();76         scanf("%d", &m);77         for(int i = 0; i < m; i++) {78             int x;79             scanf("%d", &x);80             gee[x]++;81         }82         query[m].push_back(make_pair(c, make_hash()));83     }84     for(auto it = query.begin(); it != query.end(); it++) {85         int len = it->fi;86         count_number(len);87         for(auto vt = it->se.begin(); vt != it->se.end(); vt++) {88             int ind = vt->fi;89             ull ha = vt->se;90             ans[ind] = upper_bound(cnt.begin(), cnt.end(), ha) - lower_bound(cnt.begin(), cnt.end(), ha);91         }92     }93     for(int i = 0; i < q; i++) {94         printf("%d\n", ans[i]);95     }96     return 0;97 }