# [Gold III] aFan Event Planning [문제 링크](https://www.acmicpc.net/problem/27869) ## 문제 설명 <p>SNS <a href="https://afan.ai/">aFan</a>은 매일 게시물을 게시할 때마다 최대 한 번 <em>FANCO</em>를 제공한다. FANCO는 블록체인으로 관리되는 암호화폐이며 aFan의 다양한 상품과 서비스를 구매하는 데 사용할 수 있다.</p> <p>아인(AIN)이는 이번에 aFan에서 $N$일 동안 진행될 새로운 이벤트를 기획하고 있다. 이벤트 중 $i$번째 날에 글을 쓰면 FANCO와 함께 $E_i$개의 <em>이벤트 토큰</em>을 받을 수 있고, 받은 이벤트 토큰은 이벤트 기간 중에 열리는 이벤트 상점에서 사용할 수 있다.</p> <p>이벤트가 진행되면서 이벤트 상점의 구성이 바뀔 수 있으며, 그때마다 사람들이 얻은 모든 이벤트 토큰은 모두 초기화되어 0개가 된다.</p> <p>아인이는 앞으로 $Q$번의 테스트 동작을 해 보려고 한다. 동작에는 다음의 두 종류가 있다.</p> <ol> <li>이벤트의 $d$일차에서 $d+1$일차로 넘어가는 시점에 이벤트 상점의 구성을 바꾸기로 한다. 즉, $d+1$일차로 넘어가는 시점에 모든 이벤트 토큰이 초기화되도록 한다.</li> <li>이벤트 토큰을 하나도 가지고 있지 않던 어떤 사람이 이벤트의 $s$일차부터 $e$일차까지 매일 꾸준히 게시물을 작성했고, 그동안 이벤트 토큰을 전혀 소모하지 않았다고 하자. 이 사람이 $e$번째 날이 끝나기 직전에 가진 이벤트 토큰의 양을 구해 본다.</li> </ol> <p>1번 종류의 동작은 이후의 동작에 계속해서 영향을 준다. 즉, 1번 종류의 동작을 추가로 한다고 해서 이전에 했던 1번 동작으로 만들어진 일정이 없어지지 않는다.</p> <p>2번 종류의 동작이 주어질 때마다 예상되는 이벤트 토큰의 양을 구해 보자.</p> ## 입력 <p>첫 번째 줄에 이벤트를 진행하는 날 수 $N$과 테스트 동작의 수 $Q$가 주어진다.</p> <p>두 번째 줄에 이벤트 기간 중 각 날짜에 얻을 수 있는 이벤트 토큰의 수를 나타내는 $N$개의 정수 $E_1, E_2, \cdots, E_N$이 주어진다.</p> <p>다음 $Q$개의 줄에는 테스트 동작이 처리해야 하는 순서대로 주어진다. 각 줄에 1번 종류의 동작은 $1\,d$의 형태로 주어지며, 2번 종류의 동작은 $2\,s\,e$의 형태로 주어진다. $d, s, e$는 모두 정수이다.</p> ## 출력 <p>2번 종류의 테스트 동작이 주어질 때마다 각 줄에 예상되는 이벤트 토큰의 양을 출력한다.</p> ## 풀이 d+1을 셋에 넣고 s를 --upper_bound(e)로 설정하여 초기화 이후의 구간 s~e의 구간합을 누적합으로 출력하였다. ``` c++ #include<bits/stdc++.h> using namespace std; typedef long long ll; const int MAX = 200'001; ll preSum[MAX]; int main() { ios::sync_with_stdio(0); cin.tie(0); int n, q; cin >> n >> q; for(int i=1;i<=n;i++) { cin >> preSum[i]; preSum[i] += preSum[i-1]; } set<int> reset; reset.insert(1); while(q--) { int x; cin >> x; if(x==1) { int d; cin >> d; reset.insert(d+1); } else { int s, e; cin >> s >> e; if(reset.size()) s = max(s, *(--reset.upper_bound(e))); cout << preSum[e] - preSum[s-1] << '\n'; } } } ```