[Codeforces][Round #701][Div.2] B : Replace and Keep Sorted (C++)

https://codeforces.com/contest/1485/problem/B

Problem - B - Codeforces

 

[난이도] Div.2
[유형] 구간합

[풀이]
쿼리가 l,r 일때,
a[l],a[l+1]...a[r] 부분수열을 고려해야 한다.
l,l+1,...r 중에 한개를 선택해서 바꿀 때, 그것을 대신해서 선택할 수 있는 수들의 합을 더하는 문제이다.
주석친 부분과 같이 일일이 더했을 때 시간초과가 발생하였다.
미리 부분합을 구해놓으면 query마다 O(1)로 해결할 수 있다.
부분합 dp[i] (i=l+1~r-1): l+1부터 i번 수를 한번씩 선택했을 때 만들 수 있는 수열의 개수.
query가 l,r 인 경우
답은 1. dp[r-1]-dp[l] (l+1,l+2...,r-1 을 선택했을 때 만들 수 있는 수열의 수)
2. a[l+1]-2 (l을 선택했을 때 만들 수 있는 수열의 수)
3. k-a[r-1]-1 (r을 선택했을 때 만들 수 있는 수열의 수)
위 세가지를 더한 값이 정답이다. (l과 r을 선택할 때는 방식이 다르므로 따로 계산해준다.)

 

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
int tc;
int n,q,k,a[100003],dp[100003];
 
int main(){
    scanf("%d%d%d",&n,&q,&k);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=2;i<n;i++){
        dp[i] = dp[i-1]+a[i+1]-a[i-1]-2;
    }
 
    while(q--){
        int l,r,ans=0;
        scanf("%d%d",&l,&r);
        if(l==r) ans=k-1;
        else{
            ans+=a[l+1]-2;
            ans+=k-a[r-1]-1;
            ans+=dp[r-1]-dp[l];
            // for(int i=l;i<=r;i++){
            //     int v;
            //     if(i==l) v = a[i+1]-2;
            //     else if(i==r) v = k-a[i-1]-1;
            //     else v = a[i+1]-a[i-1]-2;
            //     ans+=v;
            // }
        }
        printf("%d\n",ans);
    }
}

https://github.com/has2/Problem-Solving/blob/master/codeforces/Round701-Div.2/B.cpp