프로그래밍

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

[난이도] 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

https://www.acmicpc.net/problem/13422

[난이도] Gold4
[유형] 구간합

[풀이]
시작점이 0~N-1일때의 모둔 구간합을 구해주면 된다. 시작점을 바꿀때마다 구해줄 필요 없이
시작점이 i인 경우, 시작점이 i-1일때의 구간합에서 a[i-1]의 값을 빼고, a[(i+M-1)%N] 일때의 값만
더해주면 각 시작점마다 O(1)에 구할 수 있으므로 시간내에 해결이 가능하다.

#include <cstdio>
int tc,N,M,K,a[100000];
int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%d%d%d",&N,&M,&K);
        for(int i=0;i<N;i++) scanf("%d",&a[i]);
        int ans=0,sum=0;
        for(int i=0;i<M;i++) sum+=a[i];
        if(sum<K) ans++;
        if(N!=M){
            for(int i=1;i<N;i++){
                sum-=a[i-1];
                sum+=a[(i+M-1)%N];
                if(sum<K) {
                    ans++;
                }
            }
        }
        printf("%d\n",ans);
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/13422.cpp