1 条题解
-
2Root (sky1231) LV 8 MOD @ 2017-11-07 17:06:51
#include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <iomanip> #include <iostream> #include <algorithm> #include <vector> #include <deque> #include <set> #include <limits> #include <string> #include <sstream> using namespace std; const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f; int n,m,st_size; int a[100000+1]; int s[100000+1]; int st_t[2000000+1]; int st_l[2000000+1]; int st_r[2000000+1]; int st_mid[2000000+1]; int st_lc[2000000+1]; int st_rc[2000000+1]; int st_sum[2000000+1]; int cmp_1(int x,int y) { return x<y; } void build_st_1(int &now,int l,int r) { now=++st_size; st_l[now]=l; st_r[now]=r; st_mid[now]=(l+r)/2; if (l<r) { if (l<=st_mid[now]) build_st_1(st_lc[now],l,st_mid[now]); if (st_mid[now]+1<=r) build_st_1(st_rc[now],st_mid[now]+1,r); } } void copy_1(int now,int last) { st_l[now]=st_l[last]; st_r[now]=st_r[last]; st_mid[now]=st_mid[last]; st_lc[now]=st_lc[last]; st_rc[now]=st_rc[last]; st_sum[now]=st_sum[last]; } void update_st_1(int &now,int last,int p) { now=++st_size; copy_1(now,last); st_sum[now]++; if (st_l[now]<st_r[now]) { if (p<=st_mid[now]) update_st_1(st_lc[now],st_lc[last],p); else if (st_mid[now]+1<=p) update_st_1(st_rc[now],st_rc[last],p); } } int ask_st_sum_1(int now,int last,int th) { if (st_lc[now]==st_rc[now]) return s[st_l[now]]; else { int temp=st_sum[st_lc[now]]-st_sum[st_lc[last]]; if (temp>=th) return ask_st_sum_1(st_lc[now],st_lc[last],th); else if (temp<th) return ask_st_sum_1(st_rc[now],st_rc[last],th-temp); } } int main() { while (~scanf("%d%d",&n,&m)) { for (int i=1;i<=n;i++) scanf("%d",&a[i]); memcpy(s,a,sizeof(s)); sort(&s[1],&s[n+1],cmp_1); st_size=0; memset(st_t,0,sizeof(st_t)); memset(st_l,0,sizeof(st_l)); memset(st_r,0,sizeof(st_r)); memset(st_mid,0,sizeof(st_mid)); memset(st_lc,0,sizeof(st_lc)); memset(st_rc,0,sizeof(st_rc)); memset(st_sum,0,sizeof(st_sum)); build_st_1(st_t[st_size],1,n); for (int i=1;i<=n;i++) { int p=lower_bound(&s[1],&s[n+1],a[i])-(&s[0]); update_st_1(st_t[i],st_t[i-1],p); } for (int i=1;i<=m;i++) { int l,r,th; scanf("%d%d%d",&l,&r,&th); printf("%d\n",ask_st_sum_1(st_t[r],st_t[l-1],th)); } } }
- 1