本题可以用线段树+二分的方式实现。代码如下:
import java.io.IOException; import java.io.InputStreamReader; import java.io.PrintWriter; import java.io.StreamTokenizer; // Press Shift twice to open the Search Everywhere dialog and type `show whitespaces`, // then press Enter. You can now see whitespace characters in your code. public class Main { public static void main(String[] args) throws IOException { int n, q; StreamTokenizer st = new StreamTokenizer(new InputStreamReader(System.in)); st.nextToken(); n = (int) st.nval; st.nextToken(); q = (int) st.nval; int[] a = new int[n]; tree = new int[4 * n]; int[] b = new int[n + 1]; int[] cnt = new int[n + 1]; for (int i = 0; i < n; i++) { st.nextToken(); a[i] = (int) st.nval; if (a[i] <= n) { cnt[a[i]]++; if (b[a[i]] == 0) { b[a[i]]++; } } } PrintWriter writer = new PrintWriter(System.out); build(0, b, 0, n); for (int i = 0; i < q; i++) { st.nextToken(); int index = (int) st.nval-1; st.nextToken(); int value = (int) st.nval; int oldvalue = a[index]; if (oldvalue <= n) { cnt[oldvalue]--; if (cnt[oldvalue] == 0) { b[oldvalue]--; add(oldvalue, -1, 0, 0, n); } } a[index] = value; if (value <= n) { cnt[value]++; if (b[value] == 0) { b[value]++; add(value, 1, 0, 0, n); } } //二分 int left = 0, right = n; while (left < right) { int mid = (left + right) / 2; if(query(0,mid,0,0,n) == mid+1){ left = mid + 1; }else{ right = mid; } } // System.out.println(left); writer.println(left); } writer.flush(); } static int[] tree; public static int query(int l, int r, int index,int L, int R) { int ans = 0; if (l <= L && R <= r) { return tree[index]; }else { int mid = (L + R) / 2; if(mid<l){ return query(l,r,2*index+2,mid+1,R); } else if(r<=mid){ return query(l,r,2*index+1,L,mid); }else{ return query(l,mid,2*index+1,L,mid)+query(mid+1,r,2*index+2,mid+1,R); } } } public static void build(int index, int[] arr, int l, int r) { if (l == r) { tree[index] = arr[l]; return; } build(2 * index + 1, arr, l, (l + r) / 2); build(2 * index + 2, arr, (l + r) / 2 + 1, r); tree[index] = tree[2 * index + 1] + tree[2 * index + 2]; } public static void add(int l, int v, int index, int L, int R) { if (L == R) { tree[index] += v; return; } int mid = (L + R) / 2; if (l <= mid) { add(l, v, 2 * index + 1, L, mid); } else { add(l, v, 2 * index + 2, mid + 1, R); } tree[index] = tree[2 * index + 1] + tree[2 * index + 2]; } }
- 线段 Beginner AtCoder Contest Update线段beginner atcoder contest contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 328 beginner atcoder contest 334 beginner atcoder contest 332 beginner atcoder contest 327