\ # 선분 수, ST 표 \ # 낙 곡 1198 JZOJ 1714 최대 수

제목.
일종 의 데이터 구조 로 말미 구간 조회 와 단점 수정 을 만족시키다
분석 하 다.
그러면 이 선분 트 리 들 은 실현 할 수 있 지만 여기 서 ST 표 의 방법 을 말한다. 끝 에 있 는 한 점 에서 만 수정 하기 때문에 원래 의 ST 표 에 영향 을 받 지 않 는 다. 그래서 ST 표 는 코드 양 이 비교적 적은 데이터 구조 이지 만 상수 가 선분 트 리 보다 몇 배 크다.
코드 (jzoj 는 long long long 을 켜 야 합 니 다)

#include 
#include 
#include 
#include 
#define rr register
#define max(a,b) (((a)>(b))?(a):(b))
using namespace std;
int n,a[200001]; long long f[200001][21];
inline signed iut(){
    rr int ans=0,f=1; rr char c=getchar();
    while (!isdigit(c)) f=(c=='-')?-f:f,c=getchar();
    while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
    return ans*f;
}
inline void print(long long ans){
	if (ans<0) ans=-ans,putchar('-');
    if (ans>9) print(ans/10);
    putchar(ans%10+48);
}
inline void change(int u){
	f[u][0]=a[u];
	for (rr int i=1;u>=(1<<i);++i)
	    f[u][i]=max(f[u][i-1],f[u-(1<<(i-1))][i-1]);
}
inline long long getf(int x,int y){
	rr int t=log(y-x+1)/log(2);
	return max(f[y][t],f[x+(1<<t)-1][t]);
}
signed main(){
	rr long long t=0;
    for (rr int m=iut(),mod=iut();m;--m){
    	rr char c=getchar();
    	while (c!='Q'&&c!='A') c=getchar();
    	if (c=='A') a[++n]=(iut()+t)%mod,change(n);
    	else{
    		rr int l=iut();
    		if (l==1) print(t=a[n]),putchar(10);
    		else print(t=getf(n-l+1,n)),putchar(10);
        }
    }
    return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

HDU - 1166 - 적병 포진 (나무형 수조 또는 선분 수)

C 국 의 앙 숙 A 국 은 그동안 군사훈련 을 하고 있 었 기 때문에 C 국 간첩 두목 인 데 릭 과 그의 수하 인 티 디 는 또 바 빠 지기 시작 했다.A 국 가 는 해안선 을 따라 직선 으로 N 개 공병 캠프 ...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다