Advertisement
Guest User

SQRT

a guest
Feb 9th, 2016
59
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.99 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #pragma comment(linker, "/STACK:256000000")
  3. #include <iostream>
  4. #include <fstream>
  5. #include <cstdio>
  6. #include <cstdlib>
  7. #include <cmath>
  8. #include <ctime>
  9. #include <cstring>
  10. #include <algorithm>
  11. #include <vector>
  12. #include <string>
  13. #include <map>
  14. #include <set>
  15. #include <queue>
  16. #include <deque>
  17. #include <bitset>
  18. #include <unordered_map>
  19. #include <unordered_set>
  20.  
  21. using namespace std;
  22.  
  23. typedef unsigned long long ull;
  24. typedef long long ll;
  25. typedef long double ld;
  26. typedef pair<int, int> pii;
  27. typedef pair<ll, ll> pll;
  28. typedef vector<int> vi;
  29.  
  30. #define TASK ""
  31. #define forn(i, n) for (int i = 0; i < (int)n; i++)
  32. #define for1(i, n) for (int i = 1; i <= (int)n; i++)
  33. #define forq(i, s, t) for (int i = s; i <= (int)t; i++)
  34. #define ford(i, s, t) for (int i = s; i >= (int)t; i--)
  35. #define mk make_pair
  36. #define pk push_back
  37. #define all(v) v.begin(), v.end()
  38. #define TIME clock() * 1.0 / CLOCKS_PER_SEC
  39.  
  40. const double EPS = 1e-15;
  41. const double PI = acos(-1.0);
  42. const int MAXN = (int)5e4 + 1;
  43. const int MAXP = (int)1e4 + 1;
  44. const int MAXQ = (int)1e5 + 1;
  45. const int B = 500;
  46. const int INF = (int)1e9 + 7;
  47. const ll LINF = (ll)2e18 + 7;
  48. const int MOD = (int)1e9 + 7;
  49. const ull P = 239017;
  50. const ull MM = (ull)2147482661;
  51.    
  52. int solve();
  53.  
  54. int main()
  55. {
  56. #ifdef _DEBUG
  57.     freopen("input.txt", "r", stdin);
  58.     freopen("output.txt", "w", stdout);
  59.     freopen("test.txt", "w", stderr);
  60.     double tstart = TIME;
  61. #else
  62.     //freopen(TASK".in", "r", stdin), freopen(TASK".out", "w", stdout);
  63. #endif
  64.     solve();
  65. #ifdef _DEBUG
  66.     double tend = TIME;
  67.     cerr << tend - tstart << " s.\n";
  68. #endif
  69.     return 0;
  70. }
  71.  
  72. struct ask {
  73.     int l, r, num;
  74.     bool operator < (const ask q2) const{
  75.         int b1 = l / B, b2 = q2.l / B;
  76.         if (b1 == b2) return r < q2.r;
  77.         return b1 < b2;
  78.     }
  79. };
  80.  
  81. ask que[MAXQ];
  82. vi a[MAXN];
  83. int m[MAXP], ans[MAXQ];
  84.  
  85. int pl, pr, l, r, answer;
  86.  
  87. void addback() {
  88.     for (int i = pr + 1; i <= r; i++) {
  89.         for (int x : a[i]) {
  90.             answer -= m[x];
  91.             m[x] ^= 1;
  92.             answer += m[x];
  93.         }
  94.     }
  95. }
  96.  
  97. void addfront() {
  98.     for (int i = pl - 1; i >= l; i--) {
  99.         for (int x : a[i]) {
  100.             answer -= m[x];
  101.             m[x] ^= 1;
  102.             answer += m[x];
  103.         }
  104.     }
  105. }
  106.  
  107. void popfront() {
  108.     for (int i = pl; i < l; i++) {
  109.         for (int x : a[i]) {
  110.             answer -= m[x];
  111.             m[x] ^= 1;
  112.             answer += m[x];
  113.         }
  114.     }
  115. }
  116.  
  117. void popback() {
  118.     for (int i = pr; i > r; i--) {
  119.         for (int x : a[i]) {
  120.             answer -= m[x];
  121.             m[x] ^= 1;
  122.             answer += m[x];
  123.         }
  124.     }
  125. }
  126.  
  127. int solve()
  128. {
  129.     int n, q;
  130.     scanf("%d%d", &n, &q);
  131.     for1(i, n) {
  132.         int k;
  133.         scanf("%d", &k);
  134.         a[i].resize(k);
  135.         forn(j, k) {
  136.             scanf("%d", &a[i][j]);
  137.         }
  138.     }
  139.     forn(i, q) {
  140.         scanf("%d%d", &que[i].l, &que[i].r);
  141.         que[i].num = i;
  142.     }
  143.  
  144.     sort(que, que + q);
  145.     forn(i, q) {
  146.         l = que[i].l, r = que[i].r;
  147.         int num = que[i].num;
  148.         if (r > pr) addback();
  149.         if (l < pl) addfront();
  150.         if (l > pl) popfront();
  151.         if (r < pr) popback();
  152.         ans[num] = answer;
  153.         pl = l, pr = r;
  154.     }
  155.     forn(i, q) {
  156.         printf("%d\n", ans[i]);
  157.     }
  158.     return 0;
  159. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement