통 1546: NOIP 2011 객 잔 선택 (st 알고리즘 + 링크)

[제목 설명] 여 강 강변 에 n 개의 특색 있 는 객 잔 이 있 고 객 잔 은 그 위치 에 따라 1 부터 n 까지 번호 가 있 습 니 다.
모든 객 잔 은 특정한 색채 에 따라 장식 (총 k 종, 정수 0 k - 1 로 표시) 하고 모든 객 잔 에는 커피숍 이 설치 되 어 있 으 며 모든 커피숍 은 각자 의 최저 소 비 를 한다.
두 관광객 은 함께 여 강 으로 여행 을 떠 났 다. 이들 은 같은 톤 을 좋아 하고 다른 객 잔 두 개 를 시도 하고 싶 어 톤 이 같은 객 잔 두 곳 에서 각각 살기 로 했다.
저녁 에 그들 은 한 카페 를 선택 하여 커피 를 마 실 계획 이다. 커피숍 은 두 사람 이 사 는 두 개의 객 잔 사이 (그들 이 사 는 객 잔 포함) 에 있 고 커피숍 의 최저 소 비 는 p 를 초과 하지 않 는 다.
그들 은 모두 몇 가지 숙박 을 선택 하 는 방안 이 있 는 지 알 고 싶 어서 저녁 에 최소 소비 가 p 위안 을 초과 하지 않 는 카페 를 찾 을 수 있 도록 보장 한다.
【 입력 】 총 n + 1 줄 을 입력 합 니 다.
첫 번 째 줄 의 세 개의 정수 n, k, p 는 두 개의 정수 사이 에 하나의 빈 칸 으로 나 누 어 각각 객 잔 의 개수, 색조의 수량 과 받 아들 일 수 있 는 최저 소비의 최고 치 를 나타 낸다.
다음 n 줄, i + 1 줄 의 두 정수 사이 에 하나의 빈 칸 으로 나 누 어 각각 i 호 객 잔 의 장식 색조 와 i 호 객 잔 의 커피숍 의 최저 소 비 를 나타 낸다.
[출력] 출력 은 한 줄, 한 정수 만 있 고 선택 할 수 있 는 숙박 방안 의 총 수 를 나타 낸다.
[입력 사례] 5, 2, 3, 5, 1, 3, 2, 1, 4, 15 [출력 사례] 3 사고: 모든 구간 의 결 과 를 폭력 적 으로 매 거 하 는 것 은 분명 정확 하지만 2e6 의 데이터 양 이 시간 을 초과 하 는 것 도 긍정 적 이기 때문에 시간 복잡 도 는 O (n 2) O (n ^ {2}) O (n2) 보다 작 아야 합 니 다. 이 문 제 는 변화 할 만 한 가치 가 없 기 때문에 st 알고리즘 이 편리 합 니 다.매번 이 두 사람 은 색깔 이 같은 것 을 선택 하기 때문에 우 리 는 색깔 을 같은 체인 으로 처리 할 수 있 습 니 다. 가장 바깥쪽 에서 모든 색깔 을 매 거 할 수 있 습 니 다. 안쪽 은 모든 색깔 의 객 잔 수 이기 때문에 이것 은 n 보다 작 기 때문에 시간 복잡 도 는 O (n k) O (nk) O (nk) 보다 약간 작 습 니 다.그 다음 에 우 리 는 한 동네 에서 예 를 들 어 (l, r) 그의 구간 의 최소 치 는 p 보다 작 으 면 l 로 시작 하 는 구간 이 (l, r) 보다 큰 구간 에서 모두 합 법 적 이라는 것 을 알 수 있다. 예 를 들 어 (2, 4) 구간 에서 합 법 적 이 라면 (2, 5) 도 분명 할 것 이다. (2, 4) 구간 의 최소 치 는 이미 문제 의 뜻 을 만족 시 켰 기 때문이다. 코드:

#include
#include
#include
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int inf=0x3f3f3f3f;
const int N=2e6+10;
int log[N],dp[N][25],a[N],c[N],n,k,p;
vector<int>w[101];
void RMQ()
{
    log[0]=-1;
    for(int i=1;i<=n;i++)
        dp[i][0]=a[i],log[i]=log[i>>1]+1;
    for(int j=1;(1<<j)<=n;j++)
        for(int i=1;i+(1<<j)-1<=n;i++)
        dp[i][j]=min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
}
int query(int l,int r)
{
    int s=log[r-l+1];
    return min(dp[l][s],dp[r-(1<<s)+1][s]);
}
int read()
{
    int sign=1,res=0;
    char c=getchar();
    while(c<'0'||c>'9') sign=-1,c=getchar();
    while(c>='0'&&c<='9') res=res*10+c-'0',c=getchar();
    return res*sign;
}
int main()
{
    n=read();
    k=read();
    p=read();
    for(int i=1;i<=n;i++)
    {
        c[i]=read();
        a[i]=read();
        w[c[i]].push_back(i);
    }
    RMQ();
    int ans=0;
    for(int i=0;i<k;i++)
    {
        int len=w[i].size();
        //printf("%d
",len);
        for(int j=0;j<len-1;j++)
        {
            int pos=j+1;
            while(query(w[i][j],w[i][pos])>p)
            {
                pos++;
                if(pos>=len-1) break;
            }
            //printf("%d %d
",w[i][j],w[i][pos]);
            ans+=len-pos;//len-1+pos+1
        }
    }
    printf("%d
",ans);
    return 0;
}