Pagini recente » Cod sursa (job #2047204) | Cod sursa (job #2652530) | Cod sursa (job #2538954) | Cod sursa (job #2791100) | Cod sursa (job #1545522)
import java.io.FileInputStream;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintStream;
import java.util.InputMismatchException;
import java.util.Scanner;
public class Main {
public static InputReader input;
public static PrintStream output;
public static void openFiles() throws IOException {
InputStream inputStream = new FileInputStream("arbint.in");
input = new InputReader( inputStream );
output = new PrintStream("arbint.out");
}
public static class InputReader {
private InputStream stream;
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;
private SpaceCharFilter filter;
public InputReader(InputStream stream) {
this.stream = stream;
}
public int read() {
if (numChars == -1)
throw new InputMismatchException();
if (curChar >= numChars) {
curChar = 0;
try {
numChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (numChars <= 0)
return -1;
}
return buf[curChar++];
}
public int readInt() {
int c = read();
while (isSpaceChar(c))
c = read();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public boolean isSpaceChar(int c) {
if (filter != null)
return filter.isSpaceChar(c);
return isWhitespace(c);
}
public static boolean isWhitespace(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
public interface SpaceCharFilter {
public boolean isSpaceChar(int ch);
}
}
static public class Node<T extends Number & Comparable<? super T>> {
private T data;
private boolean maybe;
private int exception = -1;
Node() {
data = null;
maybe = false;
}
Node(T x){
data = x;
maybe = true;
}
Node<T> maximum(Node<T> b) {
if ( this.maybe == false )
return b;
if ( b.maybe == false )
return this;
if ( data.compareTo(b.data) > 0 ) {
return this;
}
return b;
}
T fold() {
if ( maybe == true )
return data;
return (T)(new Integer(exception));
}
public String toString() {
return fold().toString();
}
}
static public class SegTree<T extends Number & Comparable<? super T> > {
private Node<T> data;
private int begin, end;
private SegTree<T> leftSon, rightSon;
SegTree(int begin,int end,T data) {
this.begin = begin;
this.end = end;
this.data = new Node<>(data);
if ( begin == end ) {
leftSon = null;
rightSon = null;
return;
}
int middle = (begin + end) / 2;
leftSon = new SegTree<>(begin, middle, data);
rightSon = new SegTree<>(middle+1, end, data);
}
public void update(int pos,Node<T> data) {
if ( pos < begin || pos > end ) {
return;
}
if ( begin == end ) {
this.data = data;
return;
}
leftSon.update(pos,data);
rightSon.update(pos,data);
this.data = leftSon.data.maximum( rightSon.data );
}
public String toString() {
String ans = data.toString();
if ( leftSon != null ) ans += leftSon.toString();
if ( rightSon != null ) ans += rightSon.toString();
return ans;
}
public void print() {
System.out.println( toString() );
}
private Node<T> _query(int begin, int end) {
if ( this.end < begin || this.begin > end ) {
return new Node();
}
if ( begin <= this.begin && this.end <= end ) {
return this.data;
}
return leftSon._query(begin, end) . maximum( rightSon._query(begin, end) );
}
public T query(int begin, int end) {
return _query(begin, end).fold();
}
}
static public enum operation {
UPDATE ,
QUERY ,
NOTHING;
}
public static operation operationFromInt(int x){
switch ( x ) {
case 0:
return operation.QUERY;
case 1:
return operation.UPDATE;
default:
return operation.NOTHING;
}
}
public static void main(String[] args) throws IOException {
openFiles();
int n = input.readInt();
int m = input.readInt();
SegTree<Integer> tree = new SegTree<>(1,n,new Integer(0));
for (int i = 0; i < n ; ++i) {
Integer x = new Integer(input.readInt());
tree.update(i + 1, new Node<Integer>(x) );
}
for (int i = 0; i < m; ++i) {
int type = input.readInt();
switch ( operationFromInt(type) ) {
case QUERY:
int begin = input.readInt();
int end = input.readInt();
Integer ans = tree.query(begin, end);
output.println( ans );
break;
case UPDATE:
int p = input.readInt();
Integer x = new Integer(input.readInt());
tree.update(p, new Node<Integer>(x) );
break;
case NOTHING:
break;
}
}
}
}