結果
| 問題 | No.875 Range Mindex Query |
| ユーザー |
 tk55513
|
| 提出日時 | 2019-09-06 22:02:53 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
AC
|
| 実行時間 | 513 ms / 2,000 ms |
| コード長 | 27,101 bytes |
| コンパイル時間 | 3,136 ms |
| コンパイル使用メモリ | 100,472 KB |
| 実行使用メモリ | 65,492 KB |
| 最終ジャッジ日時 | 2024-06-24 17:55:05 |
| 合計ジャッジ時間 | 9,056 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 79 ms
37,932 KB |
| testcase_01 | AC | 91 ms
38,504 KB |
| testcase_02 | AC | 100 ms
39,028 KB |
| testcase_03 | AC | 84 ms
37,988 KB |
| testcase_04 | AC | 91 ms
38,336 KB |
| testcase_05 | AC | 86 ms
38,260 KB |
| testcase_06 | AC | 90 ms
38,572 KB |
| testcase_07 | AC | 102 ms
38,360 KB |
| testcase_08 | AC | 86 ms
38,456 KB |
| testcase_09 | AC | 96 ms
38,720 KB |
| testcase_10 | AC | 99 ms
38,776 KB |
| testcase_11 | AC | 463 ms
61,568 KB |
| testcase_12 | AC | 390 ms
53,012 KB |
| testcase_13 | AC | 418 ms
58,396 KB |
| testcase_14 | AC | 445 ms
62,304 KB |
| testcase_15 | AC | 475 ms
64,372 KB |
| testcase_16 | AC | 489 ms
60,884 KB |
| testcase_17 | AC | 513 ms
62,508 KB |
| testcase_18 | AC | 501 ms
65,492 KB |
ソースコード
import java.io.*;
import java.math.BigInteger;
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import static java.lang.Math.*;
import static java.lang.String.format;
public class Main {
public static void main(String[] args) {
solve();
}
final static int INF = Integer.MAX_VALUE>>1;
final static int MOD = 1_000_000_007;
final static int[] dx4 = { 0, 1, 0, -1 };
final static int[] dy4 = { 1, 0, -1, 0 };
final static int[] dx8 = {0, 1, 1, 1, 0, -1, -1, -1};
final static int[] dy8 = {1, 1, 0, -1, -1, -1, 0, 1};
final static Runnable me=()->{};
public static void solve(){
//TODO:Solve problem like ***
Scanner sc=new Scanner();
int n = sc.nextInt();
int q = sc.nextInt();
long[] a = new long[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
SegmentTree.MinSegmentTree mst=new SegmentTree.MinSegmentTree(a);
Map<Long, Integer> map = new HashMap<>();
for (int i = 0; i < n; i++) {
map.put(a[i],i);
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < q; i++) {
int x = sc.nextInt();
int l = sc.nextInt()-1;
int r = sc.nextInt()-1;
if(x==1){
long elementL=mst.getVal(l);
long elementR=mst.getVal(r);
mst.setVal(l,elementR);
mst.setVal(r,elementL);
map.put(elementL,r);
map.put(elementR,l);
}else{
long min=map.get(mst.getVal(l,r))+1;
sb.append(min + "\n");
}
}
print(sb);
}
private static abstract class SegmentTree {
private final int originSize;
private final int height;
private final long[] node;
private final long noRelationVal;
protected SegmentTree (long[] original,long noRelationVal){
this.noRelationVal=noRelationVal;
originSize = original.length;
{
int height_ = 1;
while (originSize > (1 << (height_ - 1))) {
height_++;
}
height = height_;
}
this.node = new long[ (1<<height)-1];
//まず元の配列に対応する部分のnodeを埋める
for(int i=0;i<originSize;i++){
this.node[(1<<(height-1))-1+i]=original[i];
}
for(int i=(1<<(height-1))-1+originSize;i<(1<<height)-1;i++){
this.node[i]=noRelationVal;
}
//空いているnodeを後ろから埋めていく
for(int i = (1<<(height-1))-2; i>=0; i--){
this.node[i]=marge(this.node[i*2+1],this.node[i*2+2]);
}
}
public long getVal(int a,int b){
return getVal(a,b,0,0,-1);
}
public long getVal(int a, int b, int k, int l, int r) {
//node[k]=origin上の範囲[l,r]の合計を表している
if(r < 0) r = (1<<(height-1))-1;
if(b<l||r<a) return noRelationVal;
if(a <= l && r <= b) return node[k];
long vl = getVal(a, b, 2*k+1, l, (l+r)/2);
long vr = getVal(a, b, 2*k+2, (l+r)/2+1, r);
return marge(vl,vr);
}
public long getVal(int index){
return node[(1<<(height-1))-1+index];
}
void setVal(int index,long val){
if(index<0||index>=originSize) throw new IllegalArgumentException(format("挿入位置が不正%d",index));
index=(1<<(height-1))-1+index;
node[index]=val;
while(index>0){
index=(index-1)/2;
node[index]=marge(node[2*index+1],node[2*index+2]);
}
}
protected abstract long marge(long a,long b);
@Override
public String toString(){
StringBuilder result=new StringBuilder();
result.append(format("Class:%s\n",getClass().getSimpleName()));
result.append(format("height:%d\n",height));
for(int currentHeight=1;currentHeight<=height;currentHeight++){
for(int i=(1<<(currentHeight-1))-1;i<=(1<<currentHeight)-2;i++){
result.append(format("%d ",node[i]));
}
result.append("\n");
}
return result.toString();
}
public static final class SumSegmentTree extends SegmentTree {
SumSegmentTree(long[] original){
this(original,0);
}
SumSegmentTree(long[] original,long noRelationVal){
super(original,noRelationVal);
}
@Override
public long marge(long a, long b) {
return a+b;
}
}
public static final class MinSegmentTree extends SegmentTree {
MinSegmentTree(long[] original){
this(original,Long.MAX_VALUE);
}
MinSegmentTree(long[] original,long noRelationVal){
super(original,noRelationVal);
}
@Override
public long marge(long a, long b) {
return Math.min(a,b);
}
}
public static final class MaxSegmentTree extends SegmentTree {
MaxSegmentTree(long[] original){
this(original,-Long.MIN_VALUE);
}
MaxSegmentTree(long[] original,long noRelationVal){
super(original,noRelationVal);
}
@Override
public long marge(long a, long b) {
return Math.max(a,b);
}
}
}
//runWhenEAで使う
private static Runnable func(Object... objects){
try{
assert false;
return me;
}catch(AssertionError e){
return ()->{put(objects);};
}
}
private static void print(Object... objects){
if(objects.length==1){
System.out.print(objects[0]);
}else{
System.out.print(Arrays.toString(objects));
}
}
private static void put(Object... objects) {
print(objects);
put();
}
private static void put(){
System.out.println();
}
private static void runWhenEA(Runnable runnable){
try{
assert false;
}catch(AssertionError e){
PrintStream ps=System.out;
PrintStream pse=System.err;
System.setOut(pse);
runnable.run();
System.setOut(ps);
}
}
private static void putM(String name,char[][] mat){
put("---------------------"+name+"-----------------");
for (int i = 0; i < mat.length; i++) {
put(Arrays.toString(mat[i]));
}
}
private static void putM(String name,int[][] mat){
put("---------------------"+name+"-----------------");
for (int i = 0; i < mat.length; i++) {
put(Arrays.toString(mat[i]));
}
}
private static void putM(String name,long[][] mat){
put("---------------------"+name+"-----------------");
for (int i = 0; i < mat.length; i++) {
put(Arrays.toString(mat[i]));
}
}
private static void putM(String name,boolean[][] mat){
put("---------------------"+name+"-----------------");
for (int i = 0; i < mat.length; i++) {
put(Arrays.toString(mat[i]));
}
}
final static private class Scanner {
private final InputStream in = System.in;
private final byte[] buffer = new byte[1024];
private int ptr = 0;
private int buflen = 0;
private boolean hasNextByte() {
if (ptr < buflen) {
return true;
} else {
ptr = 0;
try {
buflen = in.read(buffer);
} catch (IOException e) {
e.printStackTrace();
}
if (buflen <= 0) {
return false;
}
}
return true;
}
private int readByte() {
if (hasNextByte())
return buffer[ptr++];
else
return -1;
}
private boolean isPrintableChar(int c) {
return 33 <= c && c <= 126;
}
public boolean hasNext() {
while (hasNextByte() && !isPrintableChar(buffer[ptr]))
ptr++;
return hasNextByte();
}
public String next() {
if (!hasNext())
throw new NoSuchElementException();
StringBuilder sb = new StringBuilder();
int b = readByte();
while (isPrintableChar(b)) {
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
public long nextLong() {
if (!hasNext())
throw new NoSuchElementException();
long n = 0;
boolean minus = false;
int b = readByte();
if (b == '-') {
minus = true;
b = readByte();
}
if (b < '0' || '9' < b) {
throw new NumberFormatException();
}
while (true) {
if ('0' <= b && b <= '9') {
n *= 10;
n += b - '0';
} else if (b == -1 || !isPrintableChar(b)) {
return minus ? -n : n;
} else {
throw new NumberFormatException();
}
b = readByte();
}
}
public int nextInt() {
long nl = nextLong();
if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
throw new NumberFormatException();
return (int) nl;
}
public double nextDouble() {
return Double.parseDouble(next());
}
}
final static private class FixedIntPair {
final public int x, y;
final static public FixedIntPair ZEROS=new FixedIntPair(0,0);
FixedIntPair(int x, int y) {
this.x = x;
this.y = y;
}
public static double distance(FixedIntPair fip1,FixedIntPair fip2){
double x = (double) fip1.x - fip2.x;
double y = (double) fip1.y - fip2.y;
return Math.sqrt(x*x+y*y);
}
@Override
public int hashCode() {
return x*100000+y;
}
@Override
public boolean equals(Object obj) {
if(obj==null)return false;
if(!(obj instanceof FixedIntPair)) return false;
FixedIntPair pair=(FixedIntPair) obj;
return this.x==pair.x&&this.y==pair.y;
}
@Override
public String toString() {
return format(FixedIntPair.class.getSimpleName()+":(%d,%d)", x, y);
}
}
final static private class FixedLongPair {
final public long x, y;
final static public FixedLongPair ZEROS=new FixedLongPair(0,0);
FixedLongPair(long x, long y) {
this.x = x;
this.y = y;
}
public static double distance(FixedLongPair flp1,FixedLongPair flp2){
double x = (double) flp1.x - flp2.x;
double y = (double) flp1.y - flp2.y;
return Math.sqrt(x*x+y*y);
}
@Override
public int hashCode() {
return (int)x+(int)y;
}
@Override
public boolean equals(Object obj) {
if(obj==null)return false;
if(!(obj instanceof FixedLongPair)) return false;
FixedLongPair pair=(FixedLongPair)obj;
return this.x==pair.x&&this.y==pair.y;
}
@Override
public String toString() {
return format(FixedLongPair.class.getSimpleName()+":(%d,%d)", x, y);
}
}
final static private class Binary{
public static String toZeroPadding(int i){
return format("%"+Integer.toBinaryString(-1).length()+"s",Integer.toBinaryString(i)).replace(' ','0');
}
public static String toZeroPadding(long i){
return format("%"+Long.toBinaryString(-1).length()+"s",Long.toBinaryString(i)).replace(' ','0');
}
}
final static private class Util {
static long gcd(long a,long b){
a= abs(a);
b= abs(b);
if(a<b){
long tmp=a;
a=b;
b=tmp;
}
while(b!=0){
long r=a%b;
a=b;
b=r;
}
return a;
}
static int gcd(int a,int b){
a= abs(a);
b= abs(b);
if(a<b){
int tmp=a;
a=b;
b=tmp;
}
while(b!=0){
int r=a%b;
a=b;
b=r;
}
return a;
}
static long lcm(long a,long b){
long gcd=gcd(a,b);
long result=b/gcd;
return a*result;
}
static boolean isValidCell(int i,int j,int h,int w){
return i>=0&&i<h&&j>=0&&j<w;
}
}
}
/*
......................................................................................................................................
..................................... ________ ____ __________________________________________ .....................................
..................................... / _____/| | \ \__ ___/\_ _____/\______ \.....................................
...................................../ \ ___| | / | \| | | __)_ | _/.....................................
.....................................\ \_\ \ | / | \ | | \ | | \.....................................
..................................... \______ /______/\____|__ /____| /_______ / |____|_ /.....................................
..................................... \/ \/ \/ \/ .....................................
......................................................................................................................................
.............................................................,;'';:...................................................................
........................................................+@@@@@@@@@@@@@@'..............................................................
.....................................................#@@@##############@@@:...........................................................
...................................................@@@####################@@,.........................................................
.................................................@@#########################@@........................................................
...............................................:@############################@@.......................................................
..............................................@@######@@@#';;'#@@@############@@:.....................................................
.............................................@#####@@,````````````,@@###########@:....................................................
............................................@####@;``````````````````+@##########@....................................................
...........................................@###@:``````````````````````#@########@@...................................................
..........................................@####``````````````````````````@########@@..................................................
.........................................###@.````````````````````````````@########@+.................................................
.........................................@#@```````````````````````````````#########@.................................................
........................................@#@`````````````````````````````````########@@................................................
.......................................,@@```````````````````````````````````@#######@:...............................................
.......................................@@`````````````````````````````````````@#######@...............................................
.......................................@:````````````````````#@@'``````````````@######@+..............................................
......................................#@```````````````````@@@@@@@#````````````########@..............................................
......................................@```````````````````@@@@@@@@@@````````````@######@+.............................................
......................................@``````````````````@@@@@@@+ +```````````+#######@.............................................
.....................................;:``````````````````@@@@@@@ @````````````@######@'............................................
.....................................@``````````````````:@@@@@@@ @````````````@#######@............................................
.....................................@```,@@@#``````````;@@@@@@@ @````````````:#######@:...........................................
.....................................@``@@@@@@@@````````.@@@@@@@# ,#`````````````@#######@...........................................
.....................................@`@@@@@@@+'@````````@@@@@@@@@@@``````````````@#######@...........................................
.....................................@,@@@@@@ ,```:+:``:@@@@@@@@@.``````````````@########@..........................................
.....................................#@@@@@@@ ;@@#;,,,@``:@@@@@@@````````````````#########@..........................................
.....................................+@@@@@@@@',,,,,,,,;,```.'+;``````````````````'########@;.........................................
.....................................'@@@@',,,,,,,,,,,,,@`````````````````````````:#########@.........................................
....................................:@#,,,,,:;;;;;:,,,,,@`````````````````````````.#########@.........................................
.................................:@#@@@@#++';;;;;;;;;;;;@``````````````````````````##########+........................................
...............................#@#+;;;;;;;;;;;;;;;;;;;;':``````````````````````````##########@........................................
....................................,@#@@@@@#+'';;;;;+@#```````````````````````````##########@........................................
.....................................@``````````.,,,.``````````````````````````````############.......................................
.....................................@`````````````````````````````````````````````#######+'+#@.......................................
.....................................@`````````````````````````````````````````````##########'@.......................................
.....................................#`````````````````````````````````````````````############@#.....................................
.....................................:.````````````````````````````````````````````##############@,...................................
......................................+```````````````````````````````````````````.###############@#..................................
......................................@```````````````````````````````````````````.################@@.................................
......................................@```````````````````````````````````````````.###+##############@................................
......................................@```````````````````````````````````````````.###+###############@...............................
......................................',``````````````````````````````````````````.####'##############@@..............................
.......................................@```````````````````````````````````````````#####+##############@:.............................
.......................................@```````````````````````````````````````````#####'###############@.............................
.......................................@```````````````````````````````````````````######'################............................
.......................................#,``````````````````````````````````````````#######'##############@............................
........................................@``````````````````````````````````````````@######++##############+...........................
........................................@``````````````````````````````````````````@#######'##############@...........................
........................................@``````````````````````````````````````````@########'#############@...........................
.......................................@#'`````````````````````````````````````````@#########'##############..........................
.......................................@#@`````````````````````````````````````````+#########+'############@..........................
......................................@##@`````````````````````````````````````````.##########+'###########@..........................
......................................@##@:`````````````````````````````````````````###########+'###########..........................
.....................................:@###@`````````````````````````````````````````@###########+'+#########,.........................
.....................................@####@`````````````````````````````````````````@#############''########..........................
.....................................@####@.````````````````````````````````````````;##############+'######@..........................
.....................................@#####@`````````````````````````````````````````################@@@###+..........................
.....................................@#####@`````````````````````````````````````````@###############@..;;............................
....................................,@#####@.````````````````````````````````````````+################'...............................
....................................:#######@`````````````````````````````````````````################@...............................
....................................:#######@`````````````````````````````````````````@###############@...............................
....................................,@#######,````````````````````````````````````````:###############@...............................
.....................................@######@@`````````````````````````````````````````@##############@...............................
.....................................@######@@`````````````````````````````````````````+##############@...............................
.....................................@#####@,;;`````````````````````````````````````````@#############@...............................
.....................................@####@@..@`````````````````````````````````````````+#############@...............................
.....................................,####@...@``````````````````````````````````````````@############+...............................
......................................@##@.....@`````````````````````````````````````````:###########@,...............................
.......................................@+......@``````````````````````````````````````````@##########@................................
...............................................:#``````````````````````````````````````````##########@................................
................................................@``````````````````````````````````````````+########@,................................
................................................'+``````````````````````````````````````````@#######@.................................
.................................................@```````````````````````````````````````````@#####@:.................................
.................................................'#``````````````````````````````````````````.#####@..................................
..................................................@```````````````````````````````````````````;###@...................................
...................................................@```````````````````````````````````````````+#@'...................................
...................................................'#```````````````````````````````````````````@#....................................
....................................................##`````````````````````````````````````````@#.....................................
.....................................................#@```````````````````````````````````````@+......................................
......................................................:@;```````````````````````````````````;@,.......................................
.......................................................;@@'```````````````````````````````:@@+;.......................................
.......................................................@,,'@@'``````````````````````````@@@,,,@.......................................
......................................................@,,,,,,'@@@@;````````````````.+@@@;,,,,,@.......................................
......................................................#@+@,,,,,,,,+@@@@@@@@@@@@@@@@@;,,,,,'@@@........................................
.........................................................+,,,#',,@@..............@,,,,,,,,@...........................................
..........................................................@@@,#@@,...............:+,,,'@,,@...........................................
..................................................................................@,,,@.##............................................
...................................................................................@;@................................................
....................................................................................:.................................................
......................................................................................................................................
......................................................................................................................................
*/