Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #pragma comment(linker, "/STACK:256000000")
- #include <iostream>
- #include <fstream>
- #include <cstdio>
- #include <cstdlib>
- #include <cmath>
- #include <ctime>
- #include <cstring>
- #include <algorithm>
- #include <vector>
- #include <string>
- #include <map>
- #include <set>
- #include <queue>
- #include <deque>
- #include <bitset>
- #include <unordered_map>
- #include <unordered_set>
- using namespace std;
- typedef unsigned long long ull;
- typedef long long ll;
- typedef long double ld;
- typedef pair<int, int> pii;
- typedef pair<ll, ll> pll;
- typedef vector<int> vi;
- #define TASK ""
- #define forn(i, n) for (int i = 0; i < (int)n; i++)
- #define for1(i, n) for (int i = 1; i <= (int)n; i++)
- #define forq(i, s, t) for (int i = s; i <= (int)t; i++)
- #define ford(i, s, t) for (int i = s; i >= (int)t; i--)
- #define mk make_pair
- #define pk push_back
- #define all(v) v.begin(), v.end()
- #define TIME clock() * 1.0 / CLOCKS_PER_SEC
- const double EPS = 1e-15;
- const double PI = acos(-1.0);
- const int MAXN = (int)5e4 + 1;
- const int MAXP = (int)1e4 + 1;
- const int MAXQ = (int)1e5 + 1;
- const int B = 500;
- const int INF = (int)1e9 + 7;
- const ll LINF = (ll)2e18 + 7;
- const int MOD = (int)1e9 + 7;
- const ull P = 239017;
- const ull MM = (ull)2147482661;
- int solve();
- int main()
- {
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- freopen("test.txt", "w", stderr);
- double tstart = TIME;
- #else
- //freopen(TASK".in", "r", stdin), freopen(TASK".out", "w", stdout);
- #endif
- solve();
- #ifdef _DEBUG
- double tend = TIME;
- cerr << tend - tstart << " s.\n";
- #endif
- return 0;
- }
- struct ask {
- int l, r, num;
- bool operator < (const ask q2) const{
- int b1 = l / B, b2 = q2.l / B;
- if (b1 == b2) return r < q2.r;
- return b1 < b2;
- }
- };
- ask que[MAXQ];
- vi a[MAXN];
- int m[MAXP], ans[MAXQ];
- int pl, pr, l, r, answer;
- void addback() {
- for (int i = pr + 1; i <= r; i++) {
- for (int x : a[i]) {
- answer -= m[x];
- m[x] ^= 1;
- answer += m[x];
- }
- }
- }
- void addfront() {
- for (int i = pl - 1; i >= l; i--) {
- for (int x : a[i]) {
- answer -= m[x];
- m[x] ^= 1;
- answer += m[x];
- }
- }
- }
- void popfront() {
- for (int i = pl; i < l; i++) {
- for (int x : a[i]) {
- answer -= m[x];
- m[x] ^= 1;
- answer += m[x];
- }
- }
- }
- void popback() {
- for (int i = pr; i > r; i--) {
- for (int x : a[i]) {
- answer -= m[x];
- m[x] ^= 1;
- answer += m[x];
- }
- }
- }
- int solve()
- {
- int n, q;
- scanf("%d%d", &n, &q);
- for1(i, n) {
- int k;
- scanf("%d", &k);
- a[i].resize(k);
- forn(j, k) {
- scanf("%d", &a[i][j]);
- }
- }
- forn(i, q) {
- scanf("%d%d", &que[i].l, &que[i].r);
- que[i].num = i;
- }
- sort(que, que + q);
- forn(i, q) {
- l = que[i].l, r = que[i].r;
- int num = que[i].num;
- if (r > pr) addback();
- if (l < pl) addfront();
- if (l > pl) popfront();
- if (r < pr) popback();
- ans[num] = answer;
- pl = l, pr = r;
- }
- forn(i, q) {
- printf("%d\n", ans[i]);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement