Untitled
unknown
plain_text
a month ago
2.9 kB
1
Indexable
Never
#include<bits/stdc++.h> using namespace std; typedef int ll; #define int ll ll n1; ll mrg (ll x ,ll y ) { return min(x,y); } int xy; struct segment_tree { vector<ll> tree; void clear() { tree.clear(); } void init(int num, const vector<ll>& a) { n1 = num; tree.assign(4*n1,1e9); build(a); } void build(const vector<ll>& a, int id=0,int ns = 0, int ne = n1-1) { if(ns==ne){ tree[id] = a[ns]; return ; } int l = 2*id+1; int r = l+1; int md = ns+(ne-ns)/2; build(a,l, ns, md); build(a,r, md+1, ne); tree[id] = mrg(tree[l],tree[r]); } ll query(int qs, int qe, int id=0, int ns=0, int ne=n1-1) { if(ns>qe || qs>ne){ return 1e9; ///infnity } if(qs<=ns && qe>=ne){ return tree[id]; } int l = 2*id+1; int r = l+1; int md = ns+(ne-ns)/2; ll ndl = query(qs, qe, l, ns, md); ll ndr = query(qs, qe,r, md+1,ne); return mrg(ndl,ndr ); } void upd(int pos , int val , int id=0, int ns=0,int ne=n1-1) { if(ns>pos || pos>ne){ return; } if(ns==ne){ tree[id]=val; return ; } int l = 2*id+1; int r = l+1; int md = ns+(ne-ns)/2; upd(pos, val,l, ns, md); upd(pos, val, r, md+1, ne); tree[id] = mrg(tree[l],tree[r]); } int quer(int &l,int &r,int &xx,int id=0,int ns=0,int ne=1e6) { if (ns>xx) return -1e9; if (tree[id]>=l) return -1e9; if (ns==ne) { return ns; } int left=2*id+1,right=left+1; int md=(ns+ne)/2; if (tree[right]<l && ne<=xx) { return quer(l,r,xx,right,md+1,ne); } if (tree[right]>=l) { return quer(l,r,xx,left,ns,md); } return max(quer(l,r,xx,left,ns,md), quer(l,r,xx,right,md+1,ne)); } } ; void solve() { int n,q; cin>>n>>q; vector<int>a(n); vector<int>freq(1e6+1,-1e9); for (auto &x:a) { cin>>x; freq[x]++; } vector<vector<pair<pair<int,int>,int>>>v(1e6+1); for (int i=0;i<q;++i) { int l,r,x; cin>>l>>r>>x; l--; r--; v[r].push_back({{l,x},i}); } segment_tree st; st.init(1e6+1,freq); vector<int>ans(q,-1); for(int i=0;i<=(int)n-1;++i) { st.upd(a[i],i); for (auto [p,qind]:v[i]) { auto [l,x]=p; int an=st.quer(l,i,x); if (an<0)an=-1; ans[qind]=an; } } for (int i=0;i<q;++i) cout<<ans[i]<<'\n'; } signed main() { ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); solve(); }
Leave a Comment