[codeforce #419] B - Karen and Coffee

http://codeforces.com/contest/816/problem/B

n개의 구간정보와 q개의 정보가 있을 때 k개 이상인 부분의 개수를 뽑문 문제이다.

해당문제의 경우 n,q의 범위가 20만이기 때문에 직접전부다 해주면 시간 초과데스

일단 n개의 범위를 체크하는 테크닉 하나 

예를들어 n개의 범위들을 체크할 때 시작점을 +1 , 마지막점+1인 부분을 -1로 배열에 전처리를 해준다. 

예시인 (91 94), (92,97) , (97,99)

91	92	93	94	95	96	97	98	99	100
+1				-1
	+1						-1
						+1			-1

이라고 배열에 전 처리를 해주는것이다.

그리고 배열을 부분 합 구해준다. 

91	92	93	94	95	96	97	98	99	100
1	2	2	2	1	1	2	1	1	0

이라고 구해주면 각 배열들이 몇번 체크되었는지 O(n)시간에 처리 가능하다.

여기까지가 1차 처리

2차처리는 각 쿼리에 대해 응답을 상수시간에 해주기 주어진 조건이 k보다 더 많이 체크된 곳을 찾아준다. 

k가 2이므로 2보다 높은 부분을 다 찾아둔다 .

91	92	93	94	95	96	97	98	99	100
0	1	1	1	0	0	1	0	0	0

이제 여기서 부분합을 다시 구해준다. Psum[] (각 쿼리에 대한 응답을 상수사긴에 구하기 위함)

91	92	93	94	95	96	97	98	99	100
0	1	2	3	3	3	4	4	4	4

이렇게 처리를 해주면 예를들어 92~94사이에 k(예시에서는 2)보다 많이 체크된 구간은 sum[94]-psum[91] 을 통해 몇번 체크되는지 알 수 있다. 

#include <iostream>
using namespace std;
typedef long long ll;
ll s[200010], ans[200010];
int main() {
    int n,k,q; scanf("%d%d%d",&n,&k,&q);
    for(int i=0; i<n; i++) {
        int x,y;
        scanf("%d%d", &x,&y);
        s[x]++;
        s[y+1]--;
    }
    for(int i=1; i<=200000; i++) {
        s[i]+=s[i-1];
        if(s[i]>=k) ans[i]=ans[i-1]+1LL;
        else ans[i]=ans[i-1];
    }
    for(int i=0; i<q; i++) {
        int x,y;
        scanf("%d%d",&x,&y);
        printf("%lld\n",ans[y]-ans[x-1]);
    }
    
    return 0;
}