Hdu 4747 Mex 전달

1294 단어 DP 전달사유
제목:
대 의 는 수열 을 주 고 어떤 함수 mex (l, r) 를 수열 의 l 개 와 r 개 사이 에 나타 나 지 않 은 최소 자연 수 를 정의 하 는 것 이다.모든 구간 의 max 와.
설마...전달 하 는 사고: 매우 상세 하 다.http://www.bubuko.com/infodetail-2253192.html 아니면 곰 곰 이 생각 하고 생각 하 는 것 이 필요 하 다.
#include 
#include 
#include 
#define first fi
#define second se
#define pii pair
using namespace std;
typedef long long LL;
const int maxn = 200000+5;
int A[maxn];
int last_pos[maxn]; //last_pos[x]: x         
int full[maxn];  

int main()
{
	freopen("in.txt","r",stdin);
	int n;
	while(scanf("%d",&n) == 1&&n){
		for(int i = 1; i <= n; ++i) scanf("%d",&A[i]);
		
		memset(last_pos, 0, sizeof(last_pos));
		memset(full, 0, sizeof(full));
		
		LL temp = 0, ans = 0;
		
		for(int i = 1; i <= n; ++i){
			if(A[i] <= n){
				int cur = A[i];
				int pre = last_pos[cur];
				last_pos[cur] = i;
				for(int j = cur; j <= n; ++j){
					if(j > 0)
						full[j] = min(full[j-1], last_pos[j]);
					else
						full[j] = last_pos[j];
					if(full[j] > pre)
						temp += full[j] - pre;
					else break;
				}
			}
			ans += temp;
		}
		printf("%lld
",ans); } return 0; }

선분 나무의 뒷부분 을 배 워 서 다시 보충 하 다.

좋은 웹페이지 즐겨찾기