Untitled
unknown
c_cpp
2 years ago
2.2 kB
3
Indexable
#include <bits/stdc++.h> using namespace std; const int BASE = 1024 * 512; const int MAXN = 500005; int n, m; int p[MAXN]; pair<int, int> segTree[2 * BASE]; int cnt[MAXN]; int a[MAXN], b[MAXN], candidate[MAXN]; vector<int>S[MAXN], K[MAXN]; int ans[MAXN]; pair<int, int> combine(pair<int, int> a, pair<int, int> b) { pair<int, int> combined; if(a.first == b.first) combined = {a.first, a.second + b.second}; else if(a.second > b.second) combined = {a.first, a.second - b.second}; else combined = {b.first, b.second - a.second}; return combined; } void buildTree() { for(int i = n; i < 2 * n; i++) { segTree[i] = {p[i - n], 1}; } for(int i = n - 1; i >= 1; i--) { segTree[i] = combine(segTree[2 * i], segTree[2 * i + 1]); } } pair<int, int> get_candidate(int a, int b, int v, int l, int r) { pair<int, int> answer; pair<int, int> empty; if(b < l || r < a) { return empty; } if(a <= l && r <= b) { return segTree[v]; } int mid = (l + r) / 2; pair<int, int> res_l = get_candidate(a, b, 2 * v, l, mid); pair<int, int> res_r = get_candidate(a, b, 2 * v + 1, mid + 1, r); return combine(res_l, res_r); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; for(int i = 0; i < n; i++) { cin >> p[i]; } bool added = false; if(n%2 == 1) { n++; added = true; } buildTree(); if(added) segTree[2 * n - 1] = {0, 0}; for(int i = 0; i < m; i++) { cin >> a[i] >> b[i]; pair<int, int> lider = get_candidate(a[i], b[i], 1, 1, n); candidate[i] = lider.first; START[a[i]].push_back(i); KONIEC[b[i]].push_back(i); } for(int i = 1; i <= n; i++) { if(!S[i].empty()) { for(int j = 0; j < START[i].size(); j++) ans[START[i].at(j)] -= cnt[candidate[START[i][j]]]; } cnt[p[i - 1]]++; if(!KONIEC[i].empty()) { for(int j = 0; j < KONIEC[i].size(); j++) ans[KONIEC[i].at(j)] += cnt[candidate[KONIEC[i][j]]]; } } for(int i = 0; i < m; i++) { if((b[i] - a[i] + 1) / 2 < ans[i]) cout << candidate[i] << '\n'; else cout << 0 << '\n'; } }
Editor is loading...