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
*/
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.