[Codeforces 1132C] Painting the Fence(Prefix sum,부분합)

[Codeforces 1132C] Painting the Fence

[1,n]구간의 펜스가 있고 총 q개의 painting(색칠) query가 들어온다. 이 q개의 query중에서 2개를 제외한 (q-2)개의 query만 선택해서 색칠된 구간의 수가 최대가 되도록 만드는 문제이다. 

구간의 합과 관련된 문제라서 lazy propagation을 써야하는 문제 같았는데 그렇게 하면 시간복잡도가 O(N^2 * logN)시간이 아슬아슬하게 터진다. 게다가 이 문제는 c번 문제였고 푼 사람수도 꽤 있었기 때문에 어떻게든 더 간단히 풀 수 있는 방법이 있다고 생각했다. 콘테스트 당시에 생각한 풀이는 총 q개의 query중에서 색칠의 기여도가 가장 적은 2개의 query를 계산해내는 것이었다. 이러면 q개 중에서 2개를 선택하는 경우의 수가 qC2이므로 벌써 q^2이 된다. 이 문제의 최대 허용 복잡도가 O(q^2)까지이므로 계산하는 과정은 단 O(1)만에 해야한다는 결론이 나온다. 나는 어떻게 O(1)만에 할 수 있는지 떠올리지 못해서 결국 풀지 못했다. 콘테가 끝나고나서 솔루션을 알아보니 위에서 말한 계산 과정을 O(1)만에 처리했다. 그 방법은 바로 Prefix sum(부분합)이었다. 

q개 중에서 2개의 구간을 선택했을 때  그 두 개의 구간은 크게 겹치거나(2개), 겹치지 않거나(1개)의 상태를 가진다. 예를 들어서 구간1은 [1,5]이고 구간2는 [3,6]이라고 한다면 겹치는 구간은 [3,5]이고 겹치지 않는 구간은 [1,3) , [5,7) 이다. 겹치는 구간이라는 뜻은 2번의 색칠 횟수(=cnt[i]라고 하자)가 차감된다는 것이고, 겹치지 않는 구간은 1만큼의 cnt[i]가 차감될 것이다. 즉 겹치는 구간에서는 cnt[i]가 2인 것의 구간의 수를 빼주고 겹치지 않는 구간에서는 cnt[i]가 1인 것의 수를 전체 칠해진 구역의 수(=total)에서 빼주면 총 칠해진 구역 수를 얻을 수 있다. 어차피 내가 제외할 구간의 수는 단 2개이기 때문에 cnt[i]가 1인 것과 2인 것만 카운트 해주면 된다. cnt[i]가 3이상인 구역은 겹친다 하더라도 최소 하나의 또다른 painter가 이미 칠해놓았기 때문에 구간의 수가 줄어들지 않는다. 부분합 배열의 특성을 독특하게 이용한 문제라고 할 수 있다. 또 하나 배워갈 점은 수직선 상에서의 선분 교차 여부를 판별하는 부분이다. 밑의 코드에 74~75줄에 나와있는 부분인데 자세한 내용은 reference에 게시물로 남겨놓았다.

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stdlib.h>
#include<stack>
using namespace std;
typedef pair<int,int> pii;
typedef pair<int,int> Cord;
typedef long long ll;
/****************************Default Template******************************/
#define SIZE 5009
// #define IMP
// #define INF
// const int MOD=
struct S{
    int a,b;
 
    S(){}
    S(int _a,int _b){
        a=_a;
        b=_b;
    }
 
    const bool operator<(const S &o) const{
        return a<o.a;
    }
};
priority_queue<int> pq;
priority_queue<int,vector<int>,greater<int>> mpq;
map<int,int> mp;
stack<int> st;
set<int> set_i;
/****************************Default Template******************************/
 
pii arr[SIZE];
int cnt[SIZE],psum_1[SIZE],psum_2[SIZE];
int main(){
    int n,q;    scanf("%d %d",&n,&q);
 
    for(int i=1 ; i<=q ; i++){
        int l,r;        scanf("%d %d",&l,&r);
        arr[i]={l,r};
 
        for(int j=l ; j<=r ; j++)
            cnt[j]++;
    }
 
    int total=0;
    for(int i=1 ; i<=n ; i++)
        if(cnt[i]) total++;
 
    for(int i=1 ; i<=n ; i++){
        psum_1[i]=psum_1[i-1]+(cnt[i]==1);
        psum_2[i]=psum_2[i-1]+(cnt[i]==2);
    }
 
    int min_val=1<<30;
    for(int i=1 ; i<=q ; i++){
        for(int j=i+1 ; j<=q ; j++){
            int tmp=0;
            int f1=arr[i].first,f2=arr[j].first,s1=arr[i].second,s2=arr[j].second;
 
            tmp+=(psum_1[s1]-psum_1[f1-1]);
            tmp+=(psum_1[s2]-psum_1[f2-1]);
 
            int l=max(f1,f2),r=min(s1,s2);
            if(l<=r) tmp+=psum_2[r]-psum_2[l-1];
            min_val=min(min_val,tmp);
        }
    }
    printf("%d\n",total-min_val); 
 
    return 0;
}