結果

問題 No.878 Range High-Element Query
コンテスト
ユーザー 37zigen
提出日時 2020-04-02 01:05:08
言語 Java
(openjdk 23)
結果
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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

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