第几小

单点修改

import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {
    static final int N = 100010;
    static final int L = (int) Math.sqrt(N + 1);
    static final int M = N / L + 10;
    static int[] bl = new int[M], br = new int[M], gid = new int[N], a = new int[N];
    static ArrayList<Integer>[] gsort = new ArrayList[M];
    static int n, m, cnt;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);

        n = sc.nextInt();
        for (int i = 1; i <= n; i++) a[i] = sc.nextInt();

        cnt = 0;
        for (int l = 1; l <= n; l += L) {
            cnt++;
            bl[cnt] = l;
            br[cnt] = Math.min(l + L - 1, n);
            gsort[cnt] = new ArrayList<>();
            for (int j = bl[cnt]; j <= br[cnt]; j++) {
                gid[j] = cnt;
                gsort[cnt].add(a[j]);
            }
            Collections.sort(gsort[cnt]);
        }

        m = sc.nextInt();
        while (m-- > 0) {
            int op = sc.nextInt();
            if (op == 1) {
                int x = sc.nextInt();
                int y = sc.nextInt();
                int id = gid[x];
                int old = a[x];
                a[x] = y;

                int index = Collections.binarySearch(gsort[id], old);
                gsort[id].remove(index);
                int pos = find(gsort[id], y);
                gsort[id].add(pos, y);
            } else {
                int l = sc.nextInt();
                int r = sc.nextInt();
                int p = sc.nextInt();
                int ans = 0;
                if (gid[l] == gid[r]) {
                    for (int i = l; i <= r; i++) {
                        if (a[i] < a[p])
                            ans++;
                    }
                } else {
                    for (int i = gid[l] + 1; i < gid[r]; i++) ans += get(i, a[p]);
                    for (int i = l; i <= br[gid[l]]; i++) {
                        if (a[i] < a[p])
                            ans++;
                    }
                    for (int i = bl[gid[r]]; i <= r; i++) {
                        if (a[i] < a[p])
                            ans++;
                    }
                }
                out.print((ans + 1) + " ");
            }
        }
        out.flush();
    }

    //寻找v的位置
    static int find(ArrayList<Integer> list, int v) {
        int l = 0, r = list.size() - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (list.get(mid) >= v) r = mid;
            else l = mid + 1;
        }
        if (list.get(r) >= v) return r;
        else return r + 1;
    }

    //寻找最后一个<v
    static int get(int id, int v) {
        int l = 0, r = gsort[id].size() - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (gsort[id].get(mid) < v) l = mid;
            else r = mid - 1;
        }
        if (gsort[id].get(r) < v) return r + 1;
        else return 0;
    }
}

区间修改添加区间修改逻辑即可lazy