Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define ll long long
- using namespace std;
- const ll Base1 = 179057;
- const ll Base2 = 199909;
- const ll Mod1 = 998244353;
- const ll Mod2 = 1e5 + 7;
- const int N = 1e5 + 10;
- vector<ll> S[N];
- map<ll, vector<int>> Hash;
- void Inter(vector<ll> &a, vector<ll> &b, ll &Cur)
- {
- map<ll, ll> Cnt;
- for (auto i : a) Cnt[i]++;
- for (auto i : b) Cnt[i]++;
- for (auto i : Cnt){
- if (i.second < 2) continue;
- Cur = (Cur * Base1 ^ i.first)%Mod1;
- Cur = (Cur * Base2 ^ i.first)%Mod2;
- }
- }
- int main()
- {
- ios::sync_with_stdio(0);
- cin.tie(0); cout.tie(0);
- int n; cin >> n;
- int q; cin >> q;
- for (int i = 1; i <= n; i++)
- {
- int m; cin >> m;
- for (int j = 0; j < m; j++){
- ll x; cin >> x;
- S[i].push_back(x);
- }
- sort(S[i].begin(), S[i].end());
- ll Cur = 0;
- for (ll j : S[i]){
- Cur = (Cur * Base1 ^ j)%Mod1;
- Cur = (Cur * Base2 ^ j)%Mod2;
- }
- Hash[Cur].push_back(i);
- }
- while(q--)
- {
- int x; cin >> x;
- int y; cin >> y;
- int L; cin >> L;
- int R; cin >> R;
- ll Cur = 0;
- Inter(S[x], S[y], Cur);
- cout << upper_bound(Hash[Cur].begin(), Hash[Cur].end(), R) - lower_bound(Hash[Cur].begin(), Hash[Cur].end(), L) << '\n';
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement