제출 #996238

#제출 시각아이디문제언어결과실행 시간메모리
996238dubabubaIndex (COCI21_index)C++14
110 / 110
664 ms137080 KiB
#include <bits/stdc++.h> using namespace std; struct tree { int sum; tree *lc, *rc; tree() : sum(0), lc(nullptr), rc(nullptr) {}; tree(int x) : sum(x), lc(nullptr), rc(nullptr) {}; tree(tree *L, tree *R) { sum = 0; lc = L, rc = R; if(lc) sum += lc->sum; if(rc) sum += rc->sum; } }; const int mxn = 2e5 + 10; int sum(tree *sus) { return sus->sum; } int a[mxn], n, q; tree *root[mxn]; tree *build(int tl, int tr) { if(tl == tr) return new tree(0); int tm = (tl + tr) / 2; return new tree(build(tl, tm), build(tm + 1, tr)); } tree *upt(tree *sus, int tl, int tr, int pos, int add) { if(tl == tr) return new tree(sum(sus) + add); int tm = (tl + tr) / 2; if(pos <= tm) { tree *LC = upt(sus->lc, tl, tm, pos, add); return new tree(LC, sus->rc); } else { tree *RC = upt(sus->rc, tm + 1, tr, pos, add); return new tree(sus->lc, RC); } return nullptr; } int query(tree *L, tree *R, int tl, int tr, int adder) { if(tl == tr) return tr; int tm = (tl + tr) / 2; int cnt = sum(R->rc) - sum(L->rc) + adder; // cout << "(" << tl << ") " << tm + 1 << " to " << tr << " = " << cnt << endl; if(tm + 1 > cnt) return query(L->lc, R->lc, tl, tm, cnt); return query(L->rc, R->rc, tm + 1, tr, adder); } void print(tree *sus, int tl, int tr) { // cout << tl << " -> " << tr << ": " << sum(sus) << endl; if(tl == tr) return; int tm = (tl + tr) / 2; print(sus->lc, tl, tm); print(sus->rc, tm + 1, tr); } int main() { cin >> n >> q; root[0] = build(1, n); for(int i = 1; i <= n; i++) { cin >> a[i]; root[i] = upt(root[i - 1], 1, n, a[i], 1); // print(root[i], 1, n); // cout << endl; } while(q--) { int l, r; cin >> l >> r; // cout << "query: " << l << ' ' << r << endl; cout << query(root[l - 1], root[r], 1, n, 0) << endl; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...