Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package codechef;
- import java.io.*;
- import java.util.*;
- public class Main4 {
- public static void main(String[] args) {
- StdIn in = new StdIn();
- StringBuilder output = new StringBuilder();
- int n=in.nextInt(), q=in.nextInt(), sqrt=(int)(Math.sqrt(n)+0.0001), maxDist=100;
- long[] a = new long[n], a2 = new long[(n-1)/sqrt+1];
- for(int i=0; i<n; ++i)
- a[i] = in.nextLong();
- int[] nxt = new int[n], nxt2 = new int[n], jmps = new int[n];
- Stack<Integer> stack = new Stack<Integer>();
- for(int i=n-1; i>=0; --i) {
- int top=-1;
- while(!stack.isEmpty()&&(a[(top=stack.peek())]<=a[i]||top-i>maxDist))
- stack.pop();
- if(stack.isEmpty())
- nxt[i]=-1;
- else
- nxt[i]=top;
- stack.add(i);
- }
- stack.clear();
- for(int i=0; i<a2.length; ++i) {
- for(int j=Math.min(sqrt-1, n-sqrt*i-1); j>=0; --j) {
- int top=-1;
- while(!stack.isEmpty()&&(a[(top=stack.peek())]<=a[i*sqrt+j]||top-(i*sqrt+j)>maxDist))
- stack.pop();
- if(stack.isEmpty()) {
- nxt2[i*sqrt+j]=-1;
- jmps[i*sqrt+j]=0;
- } else {
- nxt2[i*sqrt+j]=nxt2[top]==-1?top:nxt2[top];
- jmps[i*sqrt+j]=jmps[top]+1;
- }
- stack.add(i*sqrt+j);
- }
- stack.clear();
- }
- for(int q_i=0; q_i<q; ++q_i) {
- if(in.nextInt()==1) {
- int i=in.nextInt()-1, k=in.nextInt();
- while(k>0) {
- if(nxt2[i]==-1||jmps[i]>k) {
- if(nxt[i]==-1)
- break;
- else {
- i=nxt[i];
- --k;
- }
- } else {
- k-=jmps[i];
- i=nxt2[i];
- }
- }
- output.append(i+1).append('\n');
- } else {
- int l=in.nextInt()-1, r=in.nextInt()-1, x=in.nextInt(), lB=(l-1)/sqrt+1, rB=(r+1)/sqrt-1;
- int i2=0;
- while((i2+1)*sqrt<=l-1) {
- a2[i2]-=x;
- ++i2;
- }
- i2*=sqrt;
- for(; i2<=l-1; ++i2)
- a[i2]-=x;
- i2=0;
- while((i2+1)*sqrt<=r) {
- a2[i2]+=x;
- ++i2;
- }
- i2*=sqrt;
- for(; i2<=r; ++i2)
- a[i2]+=x;
- /*for(int i=0; i<n; ++i)
- System.out.print(a[i]+a2[i/sqrt]+" ");
- System.out.println();*/
- for(int i=Math.min(l+maxDist, n-1); i>=Math.max(l-maxDist, 0); --i) {
- int top=-1;
- while(!stack.isEmpty()&&(a[(top=stack.peek())]+a2[top/sqrt]<=a[i]+a2[i/sqrt]||top-i>maxDist))
- stack.pop();
- if(i<=l) {
- if(stack.isEmpty())
- nxt[i]=-1;
- else
- nxt[i]=top;
- }
- stack.push(i);
- }
- stack.clear();
- for(int i=Math.min(r+maxDist, n-1); i>=Math.max(r-maxDist, 0); --i) {
- int top=-1;
- while(!stack.isEmpty()&&(a[(top=stack.peek())]+a2[top/sqrt]<=a[i]+a2[i/sqrt]||top-i>maxDist))
- stack.pop();
- if(i<=r) {
- if(stack.isEmpty())
- nxt[i]=-1;
- else
- nxt[i]=top;
- }
- stack.push(i);
- }
- stack.clear();
- for(int i=Math.max((l-maxDist)/sqrt, 0); i<=l/sqrt; ++i) {
- for(int j=Math.min(sqrt-1, n-sqrt*i-1); j>=0; --j) {
- int top=-1, newI=i*sqrt+j;
- while(!stack.isEmpty()&&(a[(top=stack.peek())]<=a[newI]||top-(newI)>maxDist))
- stack.pop();
- if(stack.isEmpty()) {
- nxt2[newI]=-1;
- jmps[newI]=0;
- } else {
- nxt2[newI]=nxt2[top]==-1?top:nxt2[top];
- jmps[newI]=jmps[top]+1;
- }
- stack.push(newI);
- }
- stack.clear();
- }
- for(int i=Math.max((r-maxDist)/sqrt, 0); i<=r/sqrt; ++i) {
- for(int j=Math.min(sqrt-1, n-sqrt*i-1); j>=0; --j) {
- int top=-1, newI=i*sqrt+j;
- while(!stack.isEmpty()&&(a[(top=stack.peek())]<=a[newI]||top-(newI)>maxDist))
- stack.pop();
- if(stack.isEmpty()) {
- nxt2[newI]=-1;
- jmps[newI]=0;
- } else {
- nxt2[newI]=nxt2[top]==-1?top:nxt2[top];
- jmps[newI]=jmps[top]+1;
- }
- stack.push(newI);
- }
- stack.clear();
- }
- }
- }
- System.out.println(output);
- }
- interface Input {
- public String next();
- public String nextLine();
- public int nextInt();
- public long nextLong();
- public double nextDouble();
- }
- static class StdIn implements Input {
- final private int BUFFER_SIZE = 1 << 16;
- private DataInputStream din;
- private byte[] buffer;
- private int bufferPointer, bytesRead;
- public StdIn() {
- din = new DataInputStream(System.in);
- buffer = new byte[BUFFER_SIZE];
- bufferPointer = bytesRead = 0;
- }
- public StdIn(String filename) {
- try{
- din = new DataInputStream(new FileInputStream(filename));
- } catch(Exception e) {
- throw new RuntimeException();
- }
- buffer = new byte[BUFFER_SIZE];
- bufferPointer = bytesRead = 0;
- }
- public String next() {
- int c;
- while((c=read())!=-1&&(c==' '||c=='\n'||c=='\r'));
- StringBuilder s = new StringBuilder();
- while (c != -1)
- {
- if (c == ' ' || c == '\n'||c=='\r')
- break;
- s.append((char)c);
- c=read();
- }
- return s.toString();
- }
- public String nextLine() {
- int c;
- while((c=read())!=-1&&(c==' '||c=='\n'||c=='\r'));
- StringBuilder s = new StringBuilder();
- while (c != -1)
- {
- if (c == '\n'||c=='\r')
- break;
- s.append((char)c);
- c = read();
- }
- return s.toString();
- }
- public int nextInt() {
- int ret = 0;
- byte c = read();
- while (c <= ' ')
- c = read();
- boolean neg = (c == '-');
- if (neg)
- c = read();
- do
- {
- ret = ret * 10 + c - '0';
- } while ((c = read()) >= '0' && c <= '9');
- if (neg)
- return -ret;
- return ret;
- }
- public long nextLong() {
- long ret = 0;
- byte c = read();
- while (c <= ' ')
- c = read();
- boolean neg = (c == '-');
- if (neg)
- c = read();
- do {
- ret = ret * 10 + c - '0';
- }
- while ((c = read()) >= '0' && c <= '9');
- if (neg)
- return -ret;
- return ret;
- }
- public double nextDouble() {
- double ret = 0, div = 1;
- byte c = read();
- while (c <= ' ')
- c = read();
- boolean neg = (c == '-');
- if (neg)
- c = read();
- do {
- ret = ret * 10 + c - '0';
- }
- while ((c = read()) >= '0' && c <= '9');
- if (c == '.')
- {
- while ((c = read()) >= '0' && c <= '9')
- {
- ret += (c - '0') / (div *= 10);
- }
- }
- if (neg)
- return -ret;
- return ret;
- }
- private void fillBuffer() throws IOException {
- bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
- if (bytesRead == -1)
- buffer[0] = -1;
- }
- private byte read() {
- try{
- if (bufferPointer == bytesRead)
- fillBuffer();
- return buffer[bufferPointer++];
- } catch(IOException e) {
- throw new RuntimeException();
- }
- }
- public void close() throws IOException {
- if (din == null)
- return;
- din.close();
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement