結果

問題 No.878 Range High-Element Query
ユーザー 37zigen37zigen
提出日時 2020-04-02 01:05:08
言語 Java21
(openjdk 21)
結果
AC  
実行時間 1,330 ms / 2,000 ms
コード長 2,236 bytes
コンパイル時間 3,037 ms
コンパイル使用メモリ 79,564 KB
実行使用メモリ 84,940 KB
最終ジャッジ日時 2023-09-09 20:39:18
合計ジャッジ時間 16,970 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 136 ms
55,480 KB
testcase_01 AC 203 ms
59,036 KB
testcase_02 AC 212 ms
59,136 KB
testcase_03 AC 191 ms
57,008 KB
testcase_04 AC 207 ms
56,852 KB
testcase_05 AC 219 ms
58,656 KB
testcase_06 AC 199 ms
56,704 KB
testcase_07 AC 173 ms
56,196 KB
testcase_08 AC 223 ms
58,916 KB
testcase_09 AC 219 ms
59,532 KB
testcase_10 AC 211 ms
56,768 KB
testcase_11 AC 1,224 ms
80,744 KB
testcase_12 AC 1,042 ms
78,736 KB
testcase_13 AC 1,128 ms
77,168 KB
testcase_14 AC 997 ms
76,092 KB
testcase_15 AC 1,038 ms
78,188 KB
testcase_16 AC 1,266 ms
82,572 KB
testcase_17 AC 1,306 ms
84,688 KB
testcase_18 AC 1,330 ms
84,940 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