Guest User

Untitled

a guest
Nov 6th, 2018
59
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <iostream>
  3. #include <map>
  4. #include <vector>
  5. #include <utility>
  6. #include <cmath>
  7. #include <cstring>
  8. #include <algorithm>
  9. using namespace std;
  10.  
  11. typedef long long int ll;
  12. typedef pair<ll, ll> ipair;
  13. #define mod 1000000007
  14. #define pb push_back
  15. #define mp make_pair
  16. #define ff first
  17. #define ss second
  18. #define sz size()
  19. #define ln length()
  20. #define rep(i,n) for(i=0;i<n;i++)
  21. #define fu(i,a,n) for(i=a;i<=n;i++)
  22. #define fd(i,n,a) for(i=n;i>=a;i--)
  23. #define all(a)  a.begin(),a.end()
  24. #define gi(n) scanf("%d",&n)
  25. #define gl(n) scanf("%lld",&n)
  26. #define pi(n) printf("%d",n)
  27. #define pl(n) printf("%lld",n);
  28. #define pp printf(" ")
  29. #define pn printf("\n")
  30. #define LN 31
  31. #define MAX 100005
  32.  
  33. ll dp[MAX][LN];
  34. ll queryVal(ll l, ll r) {
  35.     ll ans = 0;
  36.     ll i;
  37.     rep(i, LN) {
  38.         if(dp[r][i] - dp[l - 1][i] == r + 1 - l) {
  39.             ans|=(1 << i);
  40.         }
  41.     }
  42.     return ans;
  43. }
  44. int main() {
  45.     ll n, q;
  46.     gl(n);
  47.     gl(q);
  48.     ll i, j, k;
  49.     map<ll, ll> m;
  50.     fu(i, 1, n) {
  51.         gl(k);
  52.         rep(j, LN) {
  53.             dp[i][j] = dp[i - 1][j] + ((k >> j)&1);
  54.         }
  55.     }
  56.     fu(i, 1, n) {
  57.         ll left = i;
  58.         while(left <= n) {
  59.             ll cur = queryVal(i, left);
  60.             ll l = left;
  61.             ll u = n;
  62.             ll ans = l;
  63.             while(l <= u) {
  64.                 ll mid = (l + u) >> 1;
  65.                 ll val = queryVal(i, mid);
  66.                 if(cur == val) {
  67.                     if(mid > ans) {
  68.                         ans = mid;
  69.                     }
  70.                     l = mid + 1;
  71.                 }
  72.                 else {
  73.                     u = mid - 1;
  74.                 }
  75.             }
  76.             ll num = (ans + left - 2 * i + 2) * (ans - left + 1);
  77.             num>>=1;
  78.             m[cur]+=num;
  79.             left = ans + 1;
  80.         }
  81.     }
  82.     while(q--) {
  83.         gl(k);
  84.         pl(m[k]);
  85.         pn;
  86.     }
  87.     return 0;
  88. }
RAW Paste Data