Submission #14613

#	Time	Username	Problem	Language	Result	Execution time	Memory
14613		dydnjs	공장 (KOI13_factory)	C++98	20 / 20	223 ms	26060 KiB

factory

#include<stdio.h>
#include<algorithm>
using namespace std;
#define MAX_N 1100000
//struct S {
//	int m;
//	int i;
//};
//S a[500001];
//S b[500001];
//struct s {
//	int a;
//	int b;
//} D[500001];
int tree[1<<22];
int A[MAX_N];
int B[MAX_N];
int n;
long long lim;
///////////정올책/////////////
// -> 인덱스 트리
//void update(int n) {
//	while(n>1) {
//		if(tree[n]>tree[n/2])
//			tree[n/2]=tree[n];
//		n>>=1;
//	}
//}
//int lg_sum(int s, int e) {
//	int m=0;
//	while(s<e) {
//		m=max(m, tree[e]);
//		if(!(e%2)) e--;
//		e>>=1, s>>=1;
//	}
//	if(s==e) m=max(m, tree[s]);
//	return m;
//}
//////////////////////////////////
//이건 위키에서 긁은것. 더 짧음. -> [펜윅 트리] = [바이너리 인덱스드 트리]
int sum(int idx) {
	int s = 0;
	while(idx>0) {
		s += tree[idx];
		idx -= (idx&-idx);
	}
	return s;
}
//1~15까지의 합을 구하고 싶으면 차례대로 15번, 14번, 12번, 8번 노드를 더하면 된다.
//15, 14, 12, 8을 보면 각각 1111 -> 1110 -> 1100 -> 1000 임을 알 수 있다! 이것은 pos = pos & (pos - 1); 같은 코드를 이용하면 된다.
//이것은 제일 오른쪽의 1을 떼는 작업이다.
//따라서 부분합 하나를 구하는데에 드는 시간복잡도 역시 O(log N) 이다.
void update(int idx, int val, int N) {
	while(idx <= N) {
		tree[idx] += val;
		idx += (idx&-idx);
	}
}
//5번을 예로 들면 5, 6, 8, 16번 노드가 5번 원소를 갖고 있는데, 이진법으로 살펴보면 101, 110, 1000, 10000 이다.
//이것은 제일 오른쪽의 1의 자리에 1을 하나 더 더해주는 작업이다.
//이는 pos += (pos & -pos); 같은 코드를 이용하여 순회하면 된다. 따라서, 원소 한개를 업데이트하는 연산 역시 O(log N)이다.

//int binry_search(int k) {
//	int l=0,r=n,mid,key=k;
//	while(l<=r) {
//		mid=(l+r)/2;
//		if(key == a[mid].m) return a[mid].i;
//		else if(key < a[mid].m) r=mid-1;
//		else l=mid+1;
//	}
//}
int main() {
	//freopen("input.txt", "r" ,stdin);
	/*int i,j,res;
	for(i=1; i<=n; i++) {
	scanf("%d", &a[i].m);
	a[i].i = i;
	}
	sort(a, a+n, cmp);
	for(i=1; i<=n; i++) {
	scanf("%d", &b[i].m);
	b[i].i = binry_search(b[i].m);
	}
	for(i=0; i<n; i++) {
	D[i]=1;
	for(j=0; j<i; j++) {
	if(a[i].m>a[j].m && D[i] < D[j]+1) {
	D[i] = D[j]+1;
	if(res < D[i])
	res = D[i];
	}
	}
	}*/
	// -> O(n^2) -> 노답;;;;; 바서+LIS -> D[500001][500001] 이라 노답;;;;;
	//								  -> 그리고 O(n^2) 에도 걸림.
	//								  -> 지금과 같이 만약 D[N][N]으로 했을 때 안되는 경우, 문제가 완전 꼬여버릴 수 있다.
	//								  -> 이 정도로 꼬인다는 뜻은 답이 없다;;; 와 같은 뜻이다.
	//								  -> 창의적인 방법은 인덱스트리를 보는 것이다.!
	//								  -> 인덱스트리의 복잡도는 O(n*2), 즉 O(n) 이다.
	//								  -> 즉 LIS(최대 증가 수열)를 구현하는 것은   1. D[N][N]의 구현과
	//									 	 								     2. 인덱스트리로의 구현이 있는 것이다.
	//								  -> 인덱스트리의 구현을 살펴보자.!
	//								  -> 다음은 구종만의 알고리즘 트레이닝 북을 참조한 인덱스트리의 정의이다.
	//										= 구간 트리의 궁극적인 진화 형태는 펜윅 트리 혹은 이진 인덱스 트리라고 불리는 것입니다.
	//										  
	int i,base,t,lim;
	long long res=0;
	scanf("%d", &n);
	//for(base=1;base<n;base*=2); 리프 노드의 인덱스를 구하기 위함.
	for(i=1;i<=n;i++) {
		scanf("%d", &t);
		A[t]=i;
	}
	//A[t]가 갖는 인덱스 번호.
	for(i=1;i<=n;i++) {
		scanf("%d", &t);
		//B[A[t]]=i;
		res+=i-sum(A[t])-1;
		update(A[t],1,n);
	}
	// 2 4 1 3 5 차례로 오는데,
	// 2 다음 4면 교차점 없다. 인덱스 트리는 최소한의 노드만을 탐색하여 아래 구간의 최대 값을 찾을 수 있다.
	// 4는 4이전에 입력된 데이터들 중 4 미만의 데이터의 최대값을 빠른 시간안안에 찾을 수 있다.
	// 여기서는 그 전에 있었던값의 개수 중(i)-미만인 것이 몇개인지세서(sum(A[t]))-나자신도빼주고(-1) = 4가 들어옴으로써 추가된 교차점의 개수가 된다.
	// 즉 포인트는 sum(A[t])로 O(logn)만에 현재노드 미만의 노드에서 현재노드 보다 미만인 노드가 몇개인지 세는 것이다.

	//for(i=1;i<=n;i++) {
		//res+=i-sum(B[i])-1;
		//update(B[i],1,n);
	//} -> 이렇게 B를 따로 만들 수도 있음.
	printf("%lld\n", res);
	return 0;
}

• Subtask 1: 2.2 / 2.2
• Subtask 2: 3.4 / 3.4
• Subtask 3: 3.8 / 3.8
• Subtask 4: 4.8 / 4.8
• Subtask 5: 5.8 / 5.8