結果

問題 No.878 Range High-Element Query
ユーザー 37zigen37zigen
提出日時 2020-04-02 01:05:08
言語 Java21
(openjdk 21)
結果
AC  
実行時間 1,458 ms / 2,000 ms
コード長 2,236 bytes
コンパイル時間 2,741 ms
コンパイル使用メモリ 83,444 KB
実行使用メモリ 72,760 KB
最終ジャッジ日時 2024-06-27 13:11:12
合計ジャッジ時間 17,131 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 126 ms
40,340 KB
testcase_01 AC 214 ms
43,304 KB
testcase_02 AC 213 ms
43,356 KB
testcase_03 AC 202 ms
42,320 KB
testcase_04 AC 215 ms
43,296 KB
testcase_05 AC 218 ms
43,480 KB
testcase_06 AC 192 ms
42,252 KB
testcase_07 AC 197 ms
42,068 KB
testcase_08 AC 225 ms
43,644 KB
testcase_09 AC 216 ms
43,312 KB
testcase_10 AC 205 ms
42,784 KB
testcase_11 AC 1,407 ms
70,060 KB
testcase_12 AC 1,182 ms
68,004 KB
testcase_13 AC 1,228 ms
67,276 KB
testcase_14 AC 1,044 ms
63,260 KB
testcase_15 AC 1,149 ms
67,252 KB
testcase_16 AC 1,400 ms
70,936 KB
testcase_17 AC 1,458 ms
71,728 KB
testcase_18 AC 1,437 ms
72,760 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

class SUM{
	int n=1;
	int[] v;
	
	public SUM(int n_) {
		while(n<n_)n*=2;
		v=new int[2*n];
	}
	
	void addVal(int k) {
		k+=n;
		++v[k];
		while(k!=1) {
			k/=2;
			v[k]=v[2*k]+v[2*k+1];
		}
	}
	
	int query(int a,int b) {
		a+=n;
		b+=n;
		int ret=0;
		while(a<b) {
			if(a%2==1) {
				ret+=v[a++];
			}
			if(b%2==1) {
				ret+=v[--b];
			}
			a/=2;
			b/=2;
		}
		return ret;
	}
}


class RMQ{
	int n=1;
	int[] v;
	
	public RMQ(int n_) {
		while(n<n_)n*=2;
		v=new int[2*n];
		Arrays.fill(v, -1);
	}
	
	void setVal(int k,int val) {
		k+=n;
		v[k]=val;
		while(k!=1) {
			k/=2;
			v[k]=Math.max(v[2*k], v[2*k+1]);
		}
	}
	
	int query(int a,int b) {
		a+=n;
		b+=n;
		int ret=-1;
		while(a<b) {
			if(a%2==1) {
				ret=Math.max(ret, v[a++]);
			}
			if(b%2==1) {
				ret=Math.max(ret, v[--b]);
			}
			a/=2;
			b/=2;
		}
		return ret;
	}
}

class Main {
	public static void main(String[] args) {
		new Main().run();
	}
	
	void run() {
		Scanner sc=new Scanner(System.in);
		int N=sc.nextInt();
		int Q=sc.nextInt();
		int[] a=new int[N];
		RMQ rmq=new RMQ(N);
		SUM sum=new SUM(N);
		int[] pos=new int[N];
		ArrayList<Integer>[] list=new ArrayList[N];
		for(int i=0;i<N;++i)list[i]=new ArrayList<>();
		for(int i=0;i<N;++i) {
			a[i]=Integer.parseInt(sc.next())-1;
			pos[a[i]]=i;
		}
		for(int i=N-1;i>=0;--i) {
			int v=rmq.query(0, pos[i]);
			list[v+1].add(pos[i]);
			rmq.setVal(pos[i], pos[i]);
		}
		PrintWriter pw=new PrintWriter(System.out);
		int[][] query=new int[Q][];
		long[] ans=new long[Q];
		for(int i=0;i<Q;++i) {
			int type=Integer.parseInt(sc.next());
			int l=Integer.parseInt(sc.next())-1;
			int r=Integer.parseInt(sc.next())-1;
			query[i]=new int[] {l,r+1,i};
		}
		Arrays.sort(query, Comparator.comparing(v->v[0]));
		int p=0;
		for(int i=0;i<Q;++i) {
			while(p<=query[i][0]) {
				for(int v:list[p]) {
					sum.addVal(v);
				}
				++p;
			}
			ans[query[i][2]]=sum.query(query[i][0], query[i][1]);
		}
		for(int i=0;i<Q;++i) {
			pw.println(ans[i]);
		}
		pw.close();
	}
	
	static void tr(Object... objects) {
		System.out.println(Arrays.deepToString(objects));
	}

}
0