[Codeforces Round #806 (Div. 4)] F. Yet Another Problem About Pairs Satisfying an Inequality

 

 

---

※. 배열을 받았을 때 a[index] < index 를 만족하는 것만 골라낸다.

   (인덱스를 받아와 리스트에 저장한다.)

※. ai < i , aj < j 는 만족했기 때문에 i < aj 를 만족하는 것의 개수만 찾으면 된다.

※. 리스트는 배열의 인덱스를 가져왔기 때문에 오름차순으로 정렬되어 있다.

    (이분탐색이 가능하다.)

 

1. 값을 저장하는 배열을 만든다.

2. arr[index] < index 조건을 만족하는 index를 저장하는 list를 만든다.

3. 리스트에 들어있는 index 값을 찾아와서 (리스트에 들어있는 index < 값)을 만족하는 index를 찾아간다.

  (index 값은 = aj, 리스트에 index = i, aj는 j = 1 부터 시작해야된다.)

4. 리스트가 최대 20만 까지 저장될 수 있으므로 이분탐색으로 찾아준다.

  (오름차순으로 정렬되어 있는 리스트는 이분탐색의 마지막 mid 값이 조건을 만족하는 개수가 된다.)

  ( [0 , 8, 2] 이고 0 < 1 < 2 < 3 일 때 이분탐색의 마지막 start 값은 1이 된 상태에서 반복문이 종료된다.)

 

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
 	public static void main(String arg[]) throws IOException {
 		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 		StringBuilder sb = new StringBuilder();
 		int T = Integer.parseInt(br.readLine());
 		while(T --> 0) {
 			int N = Integer.parseInt(br.readLine());
 			ArrayList<Integer> list = new ArrayList<>();
 			int[] arr = new int[N];
 			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 			for(int i = 0; i < N; i++) {
 				int temp = Integer.parseInt(st.nextToken());
 				arr[i] = temp;
 				if(temp < i + 1) {
 					list.add(i+1);
 				}
 			}
 			long ans = 0;
 			for(int i = 1; i < list.size(); i++) {
 				int aj = arr[list.get(i)-1];
 				
 				int start = 0;
 				int end = i;
 				while(start < end) {
 					int mid = (start + end) / 2;
 					if(list.get(mid) < aj) {
 						start = mid + 1;
 					}
 					else {
 						end = mid;
 					}
 				}
 				ans += start;
 			}
 			sb.append(ans).append('\n');
 		}
 		System.out.println(sb);
 	}
}