BZOJ4378 POI2015 Logistyka

Description
n 길이 의 시퀀스 를 유지 합 니 다. 처음에는 0 이 었 고 다음 두 가지 동작 을 지원 합 니 다.

U k a 는 시퀀스 의 k 번 째 수 를 a 로 변경 합 니 다.

Z c s 는 이 서열 에서 c 개의 정 수 를 선택 할 때마다 1 을 빼 고 s 차 조작 을 할 수 있 는 지 물 었 다.

매번 독립 을 묻는다. 즉, 매번 질문 할 때마다 서열 을 수정 하지 않 는 다.
Input
첫 번 째 줄 은 두 개의 정수 n, m (1 < = n, m < = 1000000) 를 포함 하고 각각 서열 길이 와 조작 횟수 를 나타 낸다.
다음 m 행위 m 개 조작, 그 중 1 < = k, c < = n, 0 < = a < = 10 ^ 9, 1 < = s < = 10 ^ 9.
Output
Z 마다 질문 할 줄 을 포함 합 니 다. 가능 하 다 면 TAK 를 출력 합 니 다. 그렇지 않 으 면 NIE 를 출력 합 니 다.
Sample Input
3 8 U 1 5 U 2 7 Z 2 6 U 3 1 Z 2 6 U 2 2 Z 2 6 Z 2 1
Sample Output
NIE TAK NIE TAK
Solution：
이 데이터 구조 문제 의 관건 적 인 조작 은 두 번 째 조 에 있다. "c 개의 정 수 를 선택 하고 각각 하 나 를 줄 여 s 차 조작 을 할 수 있 는 지 물 어보 자."
처음에 나 는 '가장 많은 조작 횟수 를 구 하 는 것' 에 대한 욕심 을 고려 했 지만 앞의 c 개의 최소 치 를 우선 취하 고 앞의 c 개의 최대 치 를 우선 취 하 는 알고리즘 은 모두 문제 가 있 었 다. 그 다음 에 욕심 은 '3, 3, 3' 과 같은 데이터 에 의 해 끊 겼 다.여러 개 를 한꺼번에 업데이트 하지 않 으 면 전체 복잡 도 는 O (s) 에 이른다.×c×logn) 등급.분명히 이 변종 문 제 를 고려 하 는 것 은 본 문제 에 참고 가치 가 없다.
위의 글 에서 도 매우 뚜렷 한 전환 이 필요 하 다. 바로 s 차 조작 을 가중치 s 로 바 꾸 는 것 이다.그 다음 에 약 현학 을 배 웠 습 니 다. 우 리 는 s 차 조작 에 따라 반드시 발견 할 수 있 습 니 다. 만약 에 가중치 > = s 의 ai 가 있다 면 s 차 조작 에서 우 리 는 선택 한 c 길이 의 서열 에서 이 ai 가 항상 한 자 리 를 차지 하 게 할 수 있 습 니 다.그럼 이제 남 은 p 자리 만 어떻게 채 울 지 고민 하 겠 습 니 다.
다른 남 은 요소 에 대해 서 는 매번 작업 중 에 한 번 만 나타 날 수 있 기 때문에 이 점 들 을 ai 개 1 로 뜯 어서 s 개의 '서랍' 에 넣 을 수 밖 에 없다.ai < s 때문에 서랍 이 여러 번 놓 여 있 는 상황 이 발생 하지 않 습 니 다.그래서 다음 과 같은 추론 식 이 있다. 만족 하면
∑i−1n{ai∣ai=p∗s
이 질문 을 완성 할 수 있 습 니 다.
상기 식 을 살 펴 보면 우 리 는 s 보다 작은 소유권 값 의 sum 과 s 보다 작 지 않 은 모든 가중치 개 수 를 알 아야 한다. 일반적인 데이터 구조 로 최적화 할 수 있다.

#include 
#define M 1000005
using namespace std;
template <class temp>
inline void Rd(temp &res){
    res=0;char c;
    while(c=getchar(),c<48);
    do res=(res<<3)+(res<<1)+(c^48);
    while(c=getchar(),c>47);
}
struct Node{
    int a,b;
    char c;
}Q[M];
int n,m,A[M],res[M],rtop=0;

/*Binary Indexed Tree*/
int cnt[M];
long long sum[M];
#define lowbit(x) x&(-x)
template <class temp>
void update(temp *bit,int pos,int val){
    if(!val)return;
    while(pos<=rtop){
        bit[pos]+=val;
        pos+=lowbit(pos);
    }
}
template <class temp> 
temp query(temp *bit,int pos){
    temp ans=0;
    while(pos){
        ans+=bit[pos];
        pos-=lowbit(pos);
    }
    return ans;
}

int main(){
    char str[5]={0};
    Rd(n),Rd(m);
    res[++rtop]=0;
    for(int i=1,a,b;i<=m;i++){
        scanf("%s",str);
        Rd(a),Rd(b);
        Q[i]=(Node){a,b,str[0]};
        res[++rtop]=b;
    }
    sort(res+1,res+rtop+1);
    rtop=unique(res+1,res+rtop+1)-(res+1);

    update(cnt,1,n);
    for(int i=1;i<=n;i++)A[i]=1;

    for(int i=1;i<=m;i++){
        Q[i].b=lower_bound(res+1,res+rtop+1,Q[i].b)-res;
        int &pos_pre=A[Q[i].a],pos_now=Q[i].b;
        if(Q[i].c=='U'){//   Q[i].a        Q[i].b
            int val_pre=res[pos_pre],val_now=res[pos_now];

            update(cnt,pos_pre,-1);
            update(cnt,pos_now,1);
            update(sum,pos_pre,-val_pre);
            update(sum,pos_now,val_now);

            pos_pre=pos_now;
        }else if(Q[i].c=='Z'){//    Q[i].a   ，  Q[i].b   
            int c=Q[i].a;
            int p=n-query(cnt,pos_now-1);
            if(p>=c){
                puts("TAK");
                continue;
            }
            p=c-p;
            if(query(sum,pos_now-1)>=1ll*p*res[pos_now])puts("TAK");
            else puts("NIE");
        }
    }
}

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

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

다양한 언어의 JSON

JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...

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

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

BZOJ4378 POI2015 Logistyka

좋은 웹페이지 즐겨찾기