Educational Codeforces Round 66

Educational Codeforces Round 66 E: n n n 구간을 정하고 m m 구간을 정하고 m m 구간 중 n n n 구간에서 꺼낸 구간이 최소한 몇 개여야 모든 점을 완전히 덮어쓸 수 있는지 묻는다.dp[i][j]를 ii i 왼쪽에서 임의의 위치로 설정하고 2j2^j2j 구간에서 가장 멀리 뛸 수 있는 위치로 한다.옮기면 dp[i][j+1]=dp[dp[i][j]][j] 이다.그러면 모든 질문[l,r]에 대해 dpdpdp를 통해 뛸 구간의 최소값을 계산합니다.

#include 
using namespace std;
const int N = 5e5+7;
const int B = 19;
int dp[N][B];
// dp[i][j]    i       ，  2^j     ，
//          。
//   ：dp[i][j+1]=dp[dp[i][j]][j]
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    memset(dp, -1, sizeof(dp));
    for(int i=0; i<n; ++i) {
        int l, r;
        scanf("%d%d", &l, &r);
        dp[l][0]=max(dp[l][0], r);
    }
    for(int i=1; i<N; ++i) {
        dp[i][0] = max(dp[i-1][0], dp[i][0]);
    }
//    printf("dd: %d
", dp[8][0]);
    for(int j=1; j<B; ++j) {
        for(int i=0; i<N; ++i) {
            if(dp[i][j-1]!=-1) {
                dp[i][j] = max(dp[i][j], dp[dp[i][j-1]][j-1]);
            }
        }
    }
    for(int i=0; i<m; ++i) {
        int l, r;
        scanf("%d%d", &l, &r);
        int ans = 1;
//        printf("dp: %d
", dp[l][0]);
        for(int j=B-1; j>=0; --j) {
            if(dp[l][j]<r&&dp[l][j]!=-1) {
                l = dp[l][j];
                ans+=(1<<j);
            }
        }
//        printf("l: %d
", l);
        if(dp[l][0]<r) ans=-1;
        printf("%d
", ans);
    }
}

F:문제는 하나의 그룹을 정해서 몇 개의 자단이 하나의 배열을 형성할 수 있는지 묻는 것이다.모든 점을 열거할 수 있습니다. 이 점을 배열의 최대 값으로 설정한 다음에 이 점을 포함하는 가장 긴 구간을 분석하여 구간 내에 이 점을 제외한 모든 점이 이 점보다 작게 합니다.예를 들어 1 2 3 1 4 7 5 6 2 1 7에 대해 이 점을 분석한 것은 전체 구간이다.문제는 해부된 이 구간에 최대치7의 배열이 얼마나 되는지로 바뀌었다.우선 각 점의 가장 먼 곳에서 왼쪽으로 확장할 수 있는 위치를 계산할 수 있어 확장된 구간에 중복 요소가 하나도 없다.그러면 원수조의 모든 점을 큰 것부터 작은 것까지 매거할 수 있고 한 점a[k]에 대해 이 라인 트리를 유지할 수 있다. 라인 트리에서 i점의 확장 길이가 a[k]보다 크면i의 권한 +1이다.이렇게 하면 구간 트리에서 어떤 하위 구간의 권치와 값을 구할 수 있다. 이것은 이 구간에서 왼쪽으로 확장하면 a[k]까지 덮어쓸 수 있고 확장 길이가 a[k]보다 크며 확장 구간 내의 원소가 서로 다르다는 것을 의미한다. 그러면 길이a[k]의 배열이 형성된다.문제는 일일이 배열할 수 있는 최대치와 왼쪽으로 최대 두 개의 부등원소 구간을 확장해서 배열 총수를 계산하는 것이다.

#include 
#include 
#include 
#include 
using namespace std;
// 1 2 3 1 4 7 5 6 2 1
//                 
//                           
//       k      ，            k   
//           。
//            ，        。
const int N = 3e5+7;
int a[N], mnt[N], last[N], b[N], left[N], right[N], c[N], n;
vector<int> rext[N];
int lowbit(int x) {
    return x&-x;
}
void update(int x, int v) {
    for(;x<=n;x+=lowbit(x)) {
        c[x]+=v;
    }
}
int query(int x) {
    int res=0;
    for(;x>0;x-=lowbit(x)) {
        res+=c[x];
    }
    return res;
}
int main() {
    scanf("%d", &n);
    for(int i=1; i<=n; ++i) {
        scanf("%d", &a[i]);
        mnt[i] = max(mnt[i-1], last[a[i]]+1);
        last[a[i]]=i;
        rext[i-mnt[i]+1].push_back(i);
//        printf("rtext: %d %d
", i-mnt[i]+1, i);
        b[i]=i;
    }
    sort(b+1, b+1+n, [](int x, int y){ return a[x]>a[y]; });
    stack<int> s;
    for(int i=1; i<=n; ++i) {
        while(!s.empty()&&a[i]>a[s.top()]) s.pop();
        if(s.empty()) left[i]=1;
        else left[i]=s.top()+1;
        s.push(i);
    }
    s = stack<int>();
    for(int i=n; i>=1; --i) {
        while(!s.empty()&&a[i]>a[s.top()]) s.pop();
        if(s.empty()) right[i]=n;
        else right[i]=s.top()-1;
        s.push(i);
    }
//    for(int i=1; i<=n; ++i) {
//        printf("left: %d, right: %d
", left[i], right[i]);
//    }
    int m = n;
    long long ans=0;
//    for(int i=1; i<=n; ++i) {
//        printf("a: %d
", a[i]);
//    }
    for(int i=1; i<=n; ++i) {
        int k = b[i];
//        printf("iter: %d %d
", k, a[k]);
        while(m>=a[k]) {
            for(int p : rext[m]) {
                update(p, 1);
            }
            --m;
        }
        int lb = max(k, left[k]+a[k]-1);
        int rb = min(right[k], k+a[k]-1);
        if(rb<lb) continue;
        int res = query(rb) - query(lb-1);
//        printf("%d %d %d %d
", k, lb, rb, res);
        ans += res;
    }
    printf("%I64d
", ans);
}