poj 2104持続可能セグメントツリー区間Kは大きく変更されない
2383 ワード
poj 2104
区間k大変更なしクエリーテンプレートのみ
区間k大変更なしクエリーテンプレートのみ
#include
#include
#include
#include
#include
#include
#include
#define N 240008
#define M 5500000
using namespace std;
int n,m,rt[N];
struct Node{
int l,r,cnt;;
}tr[N<<4];
int cur;
void pushup(int x)
{
int l=tr[x].l,r=tr[x].r;
tr[x].cnt=tr[l].cnt + tr[r].cnt;
}
inline void apushup(int o) {
tr[o].cnt = tr[tr[o].l].cnt + tr[tr[o].r].cnt;
}
int build(int l,int r ) {
int k = cur++;
if (l == r) {
tr[k].cnt = 0;
return k;
}
int mid = (l + r) >> 1;
tr[k].l = build(l, mid);
tr[k].r = build(mid + 1, r);
pushup(k);
return k;
}
int update(int x,int l,int r,int pos,int val)
{
int k = cur++;
tr[k] = tr[x];
if (l == pos && r == pos) {
tr[k].cnt += val;
return k;
}
int mid = (l + r) >> 1;
if (pos <= mid)
tr[k].l = update(tr[x].l, l, mid, pos, val);
else
tr[k].r = update(tr[x].r, mid + 1, r, pos, val);
pushup(k);
return k;
}
int Ask(int l,int r,int x,int v,int kth) {
if (l == r)return l;
int mid = (l + r) >> 1;
int res = tr[tr[v].l].cnt - tr[tr[x].l].cnt;
if (kth <= res)return Ask(l, mid, tr[x].l, tr[v].l, kth);
else return Ask(mid + 1, r, tr[x].r, tr[v].r, kth - res);
}
int b[N];
int sortb[N];
int main()
{
while(~scanf("%d%d",&n,&m))
{
//init();
cur=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&b[i]);
sortb[i]=b[i];
}
sort(sortb+1,sortb+n+1);
int cnt=1;
for(int i =2;i<=n;i++)
{
if(sortb[i]!=sortb[cnt])
sortb[++cnt]=sortb[i];
}
rt[0]=build(1,cnt);
for(int i=1;i<=n;i++)
{
int p=lower_bound(sortb+1,sortb+1+cnt,b[i]) - sortb;
rt[i]=update(rt[i-1],1,cnt,p,1);
}
int l,r,k,z;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&l,&r,&k);
int idx=Ask(1,cnt,rt[l-1],rt[r],k);
printf("%d
",sortb[idx]);
}
}
return 0;
}
/*
7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3
*/