HDU 4417 슈퍼 마리 오 (나무 구분) \ # by zh
#include <iostream>
#include <cstdio>
#include <string.h>
#include <algorithm>
using namespace std;
#define M 100001
#define LL(x) (x<<1)
#define RR(x) (x<<1|1)
struct Seg_Tree
{
int left,right;
int mid()
{
return (left + right) >> 1;
}
} tt[M<<2];
int len;
int sorted[M];
int toLeft[20][M];
int val[20][M];
void build(int l,int r,int d,int idx)
{
tt[idx].left = l;
tt[idx].right = r;
if(tt[idx].left == tt[idx].right) return ;
int mid = tt[idx].mid();
int lsame = mid - l + 1;//lsame val_mid
for(int i = l ; i <= r ; i ++)
{
if(val[d][i] < sorted[mid])
{
lsame --;// (mid - l + 1) val_mid, val_mid
}
}
int lpos = l;
int rpos = mid+1;
int same = 0;
for(int i = l ; i <= r ; i ++)
{
if(i == l)
{
toLeft[d][i] = 0;//toLeft[i] [ tt[idx].left , i ]
}
else
{
toLeft[d][i] = toLeft[d][i-1];
}
if(val[d][i] < sorted[mid])
{
toLeft[d][i] ++;
val[d+1][lpos++] = val[d][i];
}
else if(val[d][i] > sorted[mid])
{
val[d+1][rpos++] = val[d][i];
}
else
{
if(same < lsame) // lsame
{
same ++;
toLeft[d][i] ++;
val[d+1][lpos++] = val[d][i];
}
else
{
val[d+1][rpos++] = val[d][i];
}
}
}
build(l,mid,d+1,LL(idx));
build(mid+1,r,d+1,RR(idx));
}
int query(int l,int r,int k,int d,int idx)
{
if(l == r)
{
return val[d][l];
}
int s;//s [ l , r ]
int ss;//ss [tt[idx].left , l-1 ]
if(l == tt[idx].left)
{
s = toLeft[d][r];
ss = 0;
}
else
{
s = toLeft[d][r] - toLeft[d][l-1];
ss = toLeft[d][l-1];
}
if(s >= k) // k , k
{
int newl = tt[idx].left + ss;
int newr = tt[idx].left + ss + s - 1;//
return query(newl,newr,k,d+1,LL(idx));
}
else
{
int mid = tt[idx].mid();
int bb = l - tt[idx].left - ss;//bb [tt[idx].left , l-1 ]
int b = r - l + 1 - s;//b [l , r]
int newl = mid + bb + 1;
int newr = mid + bb + b;
return query(newl,newr,k-s,d+1,RR(idx));
}
}
int main()
{
//freopen("input.txt","r",stdin);
int n,m,t;
scanf("%d",&t);
for(int cas=1; cas<=t; cas++)
{
scanf("%d %d",&n,&m);
printf("Case %d:
",cas);
for(int i = 1 ; i <= n ; i++)
{
scanf("%d",&val[0][i]);
sorted[i] = val[0][i];
}
sort(sorted+1,sorted+n+1);
build(1,n,0,1);
while(m--)
{
int a,b,h;
scanf("%d %d %d",&a,&b,&h);
int low=1,high=b-a+1,mid;
while(low<=high)
{
mid=(high+low)>>1;
if(query(a+1,b+1,mid,0,1)<=h)
low=mid+1;
else high=mid-1;
}
printf("%d
",low-1);
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.