阿祁的部落格

TOI 2021.11 潛力組(三) 建材(Material) Java 解題心得( 題目 )

感謝thanksone提供解題方向!

解題概念:BIT (Binary Indexed Tree)

解題方法:這題我們需要提供多組查詢，所以一開始應該會想到要用線段樹之類的資料結構，而這題其實我們可以以每個查詢的右界排序，這樣可以方便我們只要掃描一次，我們以last[i]代表一種材料上次出現的位置，當我們範圍每次往右邊移動時，我們就修改那格的值從0到1(因為被算進去)，如果之前這數字之前出現過，我們就把他上次出現的位置的值從1改到0，這樣才不會重複算到，因此我們發現這樣其實可以用BIT，每一次查詢就是sum[R]-sum[L-1]，而修改和查詢都可以在O(logn)完成。

Java參考程式碼(有更好意見可留言於下方，謝謝!)

import java.io.*;

import java.util.*;

public class zjg776 {

    public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

    public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));

    public static int r,ret,sum,idx=0;

    public static final int maxn=400005;

    public static int[] bit=new int[maxn];//維護BIT

    public static int[] last=new int[maxn];//上次位置

    public static int[] mp=new int[maxn];//輸入

    public static int[] ans=new int[maxn];//答案

    public static void main(String[] args) throws Exception {

        final int n=readint();

        for(int i=1;i<=n;i++)mp[i]=readint();

        final int q=readint();

        Q[] qy=new Q[q];

        for(int i=0;i<q;i++) {

            qy[i]=new Q(readint(),readint(),i);

        }

        Arrays.sort(qy,new Comparator<Q>() {

            //右界排序

            public int compare(Q f,Q s) {

                return f.r-s.r;

            }

        });

        for(int i=0;i<q;i++) {

            while(qy[i].r>idx) {

                idx++;//掃描

                update(idx,mp[idx]);

            }

            ans[qy[i].order]=query(qy[i].r)-query(qy[i].l-1);

            //查詢

        } 

        for(int i=0;i<q;i++) {

            bw.write(ans[i]+"\n");

        }

        bw.flush();

    }

    

    public static int query(int x) {

        sum=0;

        for(int i=x;i>0;i-=(i&-i)) {

            sum+=bit[i];

        }

        return sum;//查詢

    }

    

    public static void update(int x,int r) {

        for(int i=x;i<maxn;i+=(i&-i)) {

            bit[i]++;//0->1

        }

        if(last[r]!=0) {//如果有出現過

            for(int i=last[r];i<maxn;i+=(i&-i)) {

                bit[i]--;//1->0

            }

        }

        last[r]=x;//更新last

    }

    

    public static int readint() throws Exception {

        //輸入

        ret=0;

        r=br.read();

        while(r>47&&r<58) {

            ret*=10;

            ret+=(r&15);

            r=br.read();

        }


        return ret;

    }

}



class Q{

    //詢問

    int order,l,r;

    Q(int a,int b,int c){

        l=a;

        r=b;

        order=c;

    }

}