fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define fastio ios::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr);
  4. #define ll long long
  5. #define int ll
  6. const int mxn = (int)2e5+7;
  7. const int MOD = 998244353;
  8. #define isON(n, k) (((n) >> (k)) & 1)
  9.  
  10. void GETAC(){
  11.  
  12. int n, k, q;
  13. cin >> n >> k;
  14. vector<int> a(n);
  15. for (int& i : a) cin >> i;
  16.  
  17. cin >> q;
  18. vector<int> pre(n+1); // preprocess subarray sums
  19. for (int i(1); i <= n; ++i)
  20. pre[i] = pre[i-1] + a[i-1];
  21.  
  22. while (q--)
  23. {
  24.  
  25. int L, R, ans(0);
  26. cin >> L >> R;
  27. /*
  28.   * for (int l(L); l <= R; ++l)
  29.   for (int r(l); r <= R; ++r)
  30.   if (pre[r] - pre[l-1] == k)
  31.   ++ans;
  32.   *
  33.   */
  34. map<int, int> f; // key : sum, value : frequency sum appears
  35. f[pre[L-1]] = 1;
  36. for (int r(L); r <= R; ++r) { // right ends
  37. if (pre[r] - k >= 0)
  38. ans += f[pre[r] - k]; // left ends satisfy pre[r] - pre[l-1] == k
  39. ++f[pre[r]];
  40. }
  41. cout << ans << '\n';
  42. }
  43. }
  44.  
  45. signed main()
  46. {
  47. fastio
  48. int t(1); cin >> t;
  49. while(t--) GETAC(), cout << '\n';
  50. }
  51.  
  52.  
Success #stdin #stdout 0.01s 5436KB
stdin
1
10 5
2 3 0 0 0 2 3 1 1 0
7
1 2
1 3
1 7
1 10
2 7
2 6
3 8 
stdout
1
2
9
11
5
1
4