Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // clang-format off
- #pragma GCC optimize("Ofast")
- #pragma GCC optimize("no-stack-protector")
- #pragma GCC optimize("unroll-loops")
- #pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
- #pragma GCC optimize("fast-math")
- #define _CRT_SECURE_NO_WARNINGS
- #include <iostream>
- #include <vector>
- #include <string>
- #include <algorithm>
- #include <cmath>
- #include <stack>
- #include <iomanip>
- #include <fstream>
- #include <string>
- #include <set>
- #include <deque>
- #include <queue>
- #include <map>
- #include <bitset>
- #include <random>
- #include <list>
- #include <unordered_map>
- #include <unordered_set>
- #include <cassert>
- using namespace std;
- typedef long long ll;
- typedef short sh;
- typedef unsigned long long ull;
- typedef long double ld;
- typedef string str;
- //typedef __int128 ultraint;
- #define sqrt sqrtl
- #define F first
- #define S second
- #define endl '\n'
- #define all(vc666) vc666.begin(), vc666.end()
- #define allr(vc666) vc666.rbegin(), vc666.rend()
- //#define int long long
- #define degug(x) cerr (#x) << " " << (x) << endl;
- const ll INF = 1e18 + 3;
- const ll inf = 2e9 + 3;
- const ll ONE = 1, ZERO = 0;
- const ll mod = 998244353;
- const ll m1 = 1e9 + 575179;
- const ll m2 = 1e9 + 87;
- const ll LG = 21;
- //const ll k = 106033;
- //const ll k_sqrt = 400;
- const ll p = 106033;
- ld EPS = 1e-9;
- ld PI = 3.1415926535897932384;
- ld phi = (sqrt(5) + 1.0) / 2.0;
- mt19937 rnd(4906);
- const int N = 6e5 + 1;
- pair <int[30], ll[30]> tree[N];
- int a[N], bit;
- pair <int[30], ll[30]> elem;
- ll ans = 0;
- void build(int v, int l, int r) {
- if (l == r) {
- for (bit = 29; bit >= 0; bit--) {
- if (a[l] & (1 << bit)) {
- tree[v].first[bit] = min(tree[v].first[bit], a[l]);
- tree[v].second[bit] += a[l];
- break;
- }
- }
- }
- else {
- int m = (l + r) / 2;
- build(2 * v, l, m);
- build(2 * v + 1, m + 1, r);
- for (bit = 29; bit >= 0; bit--) {
- tree[v].first[bit] = min(tree[2 * v].first[bit], tree[2 * v + 1].first[bit]);
- tree[v].second[bit] = tree[2 * v].second[bit] + tree[2 * v + 1].second[bit];
- }
- }
- }
- void query(int v, int l, int r, int ql, int qr) {
- if (qr < l || ql > r) {
- return;
- }
- else if (ql <= l && qr >= r) {
- for (bit = 0; bit < 30; bit++) {
- elem.first[bit] = min(elem.first[bit], tree[v].first[bit]);
- elem.second[bit] += tree[v].second[bit];
- }
- return;
- }
- else {
- int m = (l + r) / 2;
- query(2 * v, l, m, ql, qr);
- query(2 * v + 1, m + 1, r, ql, qr);
- return;
- }
- }
- void solve() {
- int n, m, i, l, r;
- cin >> n >> m;
- for (i = 0; i < n; i++) {
- cin >> a[i];
- }
- for (i = 0; i < N; i++) {
- for (bit = 0; bit < 30; bit++) {
- tree[i].first[bit] = inf;
- tree[i].second[bit] = 0;
- }
- }
- build(1, 0, n - 1);
- for (i = 0; i < m; i++) {
- cin >> l >> r;
- for (bit = 0; bit < 30; bit++) {
- elem.first[bit] = inf;
- elem.second[bit] = 0;
- }
- query(1, 0, n - 1, l - 1, r - 1);
- ans = 0;
- for (bit = 0; bit < 30; bit++) {
- if (ans + ONE >= (ll)elem.first[bit]) {
- ans += elem.second[bit];
- }
- }
- cout << ans + ONE << endl;
- }
- }
- signed main() {
- #ifdef _DEBUG
- freopen("input.txt", "r ", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- ios_base::sync_with_stdio(0);
- cin.tie(NULL);
- cout.tie(NULL);
- int t = 1;
- //cin >> t;
- while (t--) solve();
- }
- //Deisgned by skimono
- //Клуб "Кольца(Серьги)"
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement