Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <iostream>
- #include <map>
- #include <vector>
- #include <utility>
- #include <cmath>
- #include <cstring>
- #include <algorithm>
- using namespace std;
- typedef long long int ll;
- typedef pair<ll, ll> ipair;
- #define mod 1000000007
- #define pb push_back
- #define mp make_pair
- #define ff first
- #define ss second
- #define sz size()
- #define ln length()
- #define rep(i,n) for(i=0;i<n;i++)
- #define fu(i,a,n) for(i=a;i<=n;i++)
- #define fd(i,n,a) for(i=n;i>=a;i--)
- #define all(a) a.begin(),a.end()
- #define gi(n) scanf("%d",&n)
- #define gl(n) scanf("%lld",&n)
- #define pi(n) printf("%d",n)
- #define pl(n) printf("%lld",n);
- #define pp printf(" ")
- #define pn printf("\n")
- #define LN 31
- #define MAX 100005
- ll dp[MAX][LN];
- ll queryVal(ll l, ll r) {
- ll ans = 0;
- ll i;
- rep(i, LN) {
- if(dp[r][i] - dp[l - 1][i] == r + 1 - l) {
- ans|=(1 << i);
- }
- }
- return ans;
- }
- int main() {
- ll n, q;
- gl(n);
- gl(q);
- ll i, j, k;
- map<ll, ll> m;
- fu(i, 1, n) {
- gl(k);
- rep(j, LN) {
- dp[i][j] = dp[i - 1][j] + ((k >> j)&1);
- }
- }
- fu(i, 1, n) {
- ll left = i;
- while(left <= n) {
- ll cur = queryVal(i, left);
- ll l = left;
- ll u = n;
- ll ans = l;
- while(l <= u) {
- ll mid = (l + u) >> 1;
- ll val = queryVal(i, mid);
- if(cur == val) {
- if(mid > ans) {
- ans = mid;
- }
- l = mid + 1;
- }
- else {
- u = mid - 1;
- }
- }
- ll num = (ans + left - 2 * i + 2) * (ans - left + 1);
- num>>=1;
- m[cur]+=num;
- left = ans + 1;
- }
- }
- while(q--) {
- gl(k);
- pl(m[k]);
- pn;
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment