#include <bits/stdc++.h> #include "floppy.h" using namespace std; struct Segtree { vector<int> seg; int n; void build(int n, int l, int r, vector<int> &init){ if(l == r){ seg[n] = init[l-1]; return; } int m = (l+r)/2; build(2*n, l, m, init); build(2*n+1, m+1, r, init); seg[n] = max(seg[2*n], seg[2*n+1]); } Segtree(vector<int> init) { n = init.size(); seg.resize(4*n); build(1, 1, n, init); // for(int i:seg) // cout << i << ' '; } int __query(int n, int l, int r, int left, int right){ // cout << n << '\n'; if(l > right || r < left) return -1; if(left <= l && r <= right) return seg[n]; int m = (l+r)/2; return max(__query(2*n, l, m, left, right), __query(2*n+1, m+1, r, left, right)); } int query(int left, int right){ return __query(1, 1, n, left, right); } }; void read_array(int subtask_id, const vector<int> &v){ int n = v.size(); vector<pair<int, int>> comp(n); for(int i=0;i<n;i++){ comp[i] = {v[i], i}; } sort(comp.begin(), comp.end()); vector<int> res(n); for(int i=0;i<n;i++){ res[comp[i].second] = i; } int l = 31 - __builtin_clz(n); string s; for(int i=0;i<n;i++){ for(int j=1<<l;j>0;j>>=1){ if(res[i] & j) s.push_back('1'); else s.push_back('0'); } } save_to_floppy(s); } vector<int> solve_queries(int subtask_id, int n, const string &bits, const vector<int> &a, const vector<int> &b){ int m = a.size(); vector<int> res(m); int l = 32 - __builtin_clz(n); vector<int> arr(n); for(int i=0;i<n;i++){ for(int j=0;j<l;j++){ if(bits[i*l+j] == '1') arr[i] += (1<<(l-j-1)); } } Segtree seg(arr); vector<int> rev(n); for(int i=0;i<n;i++){ rev[arr[i]] = i; } // cout << "here" << endl; for(int i=0;i<m;i++){ int q = seg.query(a[i]+1, b[i]+1); cout << q << ' '; res[i] = rev[q]; } return res; } // int main(){ // int n;cin>>n; // vector<int> A(n); for(int &i:A) cin>>i; // read_array(0, A); // int m;cin>>m; // vector<int> a(m), b(m); // for(int i=0;i<m;i++){ // cin>>a[i]>>b[i]; // } // vector<int> sol = solve_queries(0, n, str, a, b); // // for(int i:sol) // // cout << i << ' '; // }