Cerinta completa

You are given an array, , consisting of integers.

A segment, , is beautiful if and only if the bitwise AND of all numbers in with indices in the inclusive range of is not greater than . In other words, segment is beautiful if .

You must answer queries. Each query, , consists of integers: , , and . The answer for each is the number of beautiful segments such that and .

Input Format

The first line contains two space-separated integers, (the number of integers in ) and (the number of queries).

The second line contains space-separated integers, where the integer denotes the element of array .

Each line of the subsequent lines contains space-separated integers, , , and , respectively, describing query .

Constraints

  • holds for test cases worth at least of the problem’s score.
  • holds for test cases worth at least of the problem’s score.

Output Format

Print lines, where the line contains the number of beautiful segments for query .

Sample Input

5 3
1 2 7 3 4
1 5 3
2 4 6
3 5 2

Sample Output

13
5
2

Explanation

The beautiful segments for all queries are listed below.

Query 0: The beautiful segments are .

Query 1: The beautiful segments are .

Query 2: The beautiful segments are .

Limbajul de programare folosit: cpp14

Cod:

#include <bits/stdc++.h>
using namespace std;

struct Event {
    int v;
    int r;
    int a;
    int b;
};

struct PrefixQuery {
    int x;
    int t;
    int l;
    int id;
    int sign;
};

struct NodeData {
    vector<int> xs;
    vector<long long> bitSlope;
    vector<long long> bitConst;

    void init() {
        sort(xs.begin(), xs.end());
        xs.erase(unique(xs.begin(), xs.end()), xs.end());
        bitSlope.assign(xs.size() + 2, 0);
        bitConst.assign(xs.size() + 2, 0);
    }

    inline void bitAdd(vector<long long>& bit, int idx, long long delta) {
        int n = (int)bit.size() - 1;
        for (int i = idx; i <= n; i += i & -i) bit[i] += delta;
    }

    inline long long bitSum(const vector<long long>& bit, int idx) const {
        long long res = 0;
        for (int i = idx; i > 0; i -= i & -i) res += bit[i];
        return res;
    }

    void rangeAddLinear(int lVal, int rVal, long long slope, long long cst) {
        if (lVal > rVal || xs.empty()) return;
        int li = (int)(lower_bound(xs.begin(), xs.end(), lVal) - xs.begin()) + 1;
        int ri = (int)(upper_bound(xs.begin(), xs.end(), rVal) - xs.begin());
        if (li > ri) return;

        bitAdd(bitSlope, li, slope);
        bitAdd(bitSlope, ri + 1, -slope);
        bitAdd(bitConst, li, cst);
        bitAdd(bitConst, ri + 1, -cst);
    }

    long long pointQuery(int lVal) const {
        if (xs.empty()) return 0;
        int pos = (int)(lower_bound(xs.begin(), xs.end(), lVal) - xs.begin()) + 1;
        long long slope = bitSum(bitSlope, pos);
        long long cst = bitSum(bitConst, pos);
        return slope * lVal + cst;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    cin >> N >> Q;

    vector<int> a(N + 1);
    for (int i = 1; i <= N; ++i) cin >> a[i];

    vector<tuple<int, int, int>> queries(Q);
    for (int i = 0; i < Q; ++i) {
        int l, r, x;
        cin >> l >> r >> x;
        queries[i] = {l, r, x};
    }

    vector<Event> events;
    events.reserve((size_t)N * 20);

    vector<pair<int, int>> prev;
    prev.reserve(20);

    for (int r = 1; r <= N; ++r) {
        vector<pair<int, int>> cur;
        cur.reserve(prev.size() + 1);
        cur.push_back({a[r], r});

        for (auto &p : prev) {
            int nv = p.first & a[r];
            if (cur.back().first == nv) {
                cur.back().second = p.second;
            } else {
                cur.push_back({nv, p.second});
            }
        }

        for (int j = 0; j < (int)cur.size(); ++j) {
            int v = cur[j].first;
            int lStart = cur[j].second;
            int lEnd = (j == 0 ? r : cur[j - 1].second - 1);
            events.push_back({v, r, lStart, lEnd});
        }

        prev.swap(cur);
    }

    vector<PrefixQuery> pref;
    pref.reserve(2 * Q);

    for (int i = 0; i < Q; ++i) {
        int l, r, x;
        tie(l, r, x) = queries[i];
        pref.push_back({x, r, l, i, +1});
        pref.push_back({x, l - 1, l, i, -1});
    }

    vector<NodeData> fw(N + 1);
    for (const auto& pq : pref) {
        int t = pq.t;
        while (t > 0) {
            fw[t].xs.push_back(pq.l);
            t -= t & -t;
        }
    }
    for (int i = 1; i <= N; ++i) fw[i].init();

    auto addEvent = [&](const Event& e) {
        int len = e.b - e.a + 1;
        for (int i = e.r; i <= N; i += i & -i) {
            // L in [1, a-1] => +len
            fw[i].rangeAddLinear(1, e.a - 1, 0, len);
            // L in [a, b] => (b+1)-L
            fw[i].rangeAddLinear(e.a, e.b, -1, e.b + 1);
        }
    };

    auto prefixQuery = [&](int t, int lVal) {
        long long res = 0;
        for (int i = t; i > 0; i -= i & -i) {
            res += fw[i].pointQuery(lVal);
        }
        return res;
    };

    sort(events.begin(), events.end(), [](const Event& A, const Event& B) {
        if (A.v != B.v) return A.v < B.v;
        if (A.r != B.r) return A.r < B.r;
        if (A.a != B.a) return A.a < B.a;
        return A.b < B.b;
    });

    sort(pref.begin(), pref.end(), [](const PrefixQuery& A, const PrefixQuery& B) {
        if (A.x != B.x) return A.x < B.x;
        return A.t < B.t;
    });

    vector<long long> ans(Q, 0);
    int ptr = 0;
    for (const auto& pq : pref) {
        while (ptr < (int)events.size() && events[ptr].v <= pq.x) {
            addEvent(events[ptr]);
            ++ptr;
        }
        long long cur = (pq.t > 0 ? prefixQuery(pq.t, pq.l) : 0);
        ans[pq.id] += (long long)pq.sign * cur;
    }

    for (int i = 0; i < Q; ++i) {
        cout << ans[i] << '\n';
    }

    return 0;
}

Scor obtinut: 1.0

Submission ID: 464672216

Link challenge: https://www.hackerrank.com/challenges/beautiful-segments/problem

Beautiful Segments