阿祁的部落格

AtCoder ABC 242 pG. Range Pairing Query 解題心得( 題目 )

解題概念:莫隊算法

解題方法:這題記住目前元素數量，可以O(1)移動指標，所以總複雜度為O(N.sprt(Q))。

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

//Author:En Chi Tsung(欉恩祁)

//Date:2022/03/09

import java.util.*;

import java.io.*;

public class Main {

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

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

    public static int ret,rd,ans;

    public static double yee;

    public static int[] in=new int[1000005];

    public static int[] cnt=new int[1000005];

    public static int[] out=new int[1000005];

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

        final int n=readint();

        for(int i=1;i<=n;i++) {

            in[i]=readint();

        }

        final int q=readint();

        ooo[] qu=new ooo[q];

        int k=(int)Math.ceil(Math.pow(q,0.5));

         yee=(double)(n+2)/k;

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

            qu[i]=new ooo(readint(),readint(),i);

        }

        int L=1,R=0;

        Arrays.sort(qu,new Comparator<ooo>() {

            public int compare(ooo f,ooo s) {

                if(f.cry==s.cry) {

                    return f.r-s.r;

                }

                return f.cry-s.cry;

            }

        });

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

            while(qu[i].l<L) {

                L--;

                add(L);

            }

            while(qu[i].l>L) {

                del(L);

                L++;

            }

            while(qu[i].r>R) {

                R++;

                add(R);

            }

            while(qu[i].r<R) {

                del(R);

                R--;

            }

            out[qu[i].o]=ans;

        }

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

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

        }

        bw.flush();

    }

    

    public static void add(int x) {

        if((cnt[in[x]]&1)==1) {

            ans++;

        }

        cnt[in[x]]++;

    }

    

    public static void del(int x) {

        if((cnt[in[x]]&1)==0) {

            ans--;

        }

        cnt[in[x]]--;

    }

    

    public static int readint() throws Exception{

        ret=0;

        rd=br.read();

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

            ret*=10;

            ret+=(rd&15);

            rd=br.read();

        }

        return ret;

    }

}



class ooo{

    int l,r,cry,o;

    ooo(int lt,int rt,int q){

        l=lt;

        r=rt;

        cry=(int)(l/Main.yee);

        o=q;

    }

}