Submission #1000130

---

Source Code Expand

import java.io.*;
import java.math.*;
import java.util.*;

import static java.util.Arrays.*;

public class Main {
	private static final int mod = (int)1e9+7;

	final Random random = new Random(0);
	final IOFast io = new IOFast();

	/// MAIN CODE
	public void run() throws IOException {
//		int TEST_CASE = Integer.parseInt(new String(io.nextLine()).trim());
		int TEST_CASE = 1;
		while(TEST_CASE-- != 0) {
			int m = io.nextInt();
			char[] S = io.next();
			int n = io.nextInt();
			
//			dump("start");
			
			AVL_Persistent t = null;
			for (int i = 0; i < S.length; i++) {
				t = AVL_Persistent.insert(t, i, (byte)S[i]);
			}
			
			for (int q = 0; q < n; q++) {
//				dump(q);
				
				int A = io.nextInt();
				int B = io.nextInt();
				int C = io.nextInt();
				Pair<AVL_Persistent, AVL_Persistent> p1 = AVL_Persistent.split(t, A);
				Pair<AVL_Persistent, AVL_Persistent> p2 = AVL_Persistent.split(p1.second, B - A);
				Pair<AVL_Persistent, AVL_Persistent> p3 = AVL_Persistent.split(t, C);
				t = AVL_Persistent.merge(AVL_Persistent.merge(p3.first, p2.first), p3.second);
				if (AVL_Persistent.size(t) > m) {
					t = AVL_Persistent.split(t, m).first;
				}
			}
			print(t);
			io.out.println();
		}
	}
	
	void print(AVL_Persistent t) {
		if (t != null) {
			print(t.l);
			io.out.print((char)t.value);
			print(t.r);
		}
	}
	
	static
	class AVL_Persistent {
		int size;
		byte height;
		byte value;
		AVL_Persistent l, r;
		
		public static AVL_Persistent shallowCopy(AVL_Persistent t) {
			return t == null ? null : new AVL_Persistent(t.value, t.l, t.r);
		}
		
		public AVL_Persistent(byte value) {
			this(value, null, null);
		}
		
		public AVL_Persistent(byte value, AVL_Persistent l, AVL_Persistent r) {
			this.value = value;
			this.l = l;
			this.r = r;
			update();
		}

		public static int size(AVL_Persistent node) { return node == null ? 0 : node.size; }
		public static int height(AVL_Persistent node) { return node == null ? 0 : node.height; }
		
		void update() {
			this.size = 1;
			this.size += size(this.l) + size(this.r);
			this.height = (byte)(Math.max(height(this.l), height(this.r)) + 1);
		}
		
		public AVL_Persistent rotL() {
			assert(this.r != null);
			
			final AVL_Persistent r = shallowCopy(this.r);
			
			this.r = r.l;
			r.l = this;
			
			this.update();
			r.update();
			return r;
		}
		
		public AVL_Persistent rotR() {
			assert(this.l != null);
			
			final AVL_Persistent l = shallowCopy(this.l);
			
			this.l = l.r;
			l.r = this;
			
			this.update();
			l.update();
			return l;
		}
		
		public static AVL_Persistent balance(AVL_Persistent n) {
			int hl = height(n.l);
			int hr = height(n.r);
			
			if (hl > hr + 2) {
				n = shallowCopy(n);
				
				final int hll = height(n.l.l);
				final int hlr = height(n.l.r);
				if (hll < hlr) {
					n.l = shallowCopy(n.l).rotL();
					n = n.rotR();
				} else {
					n = n.rotR();
				}
			} else if (hr > hl + 2) {
				n = shallowCopy(n);
				
				final int hrl = height(n.r.l);
				final int hrr = height(n.r.r);
				if (hrl > hrr) {
					n.r = shallowCopy(n.r).rotR();
					n = n.rotL();
				} else {
					n = n.rotL();
				}
			} else {
				n.update();
			}
			return n;
		}
		
		public static
		AVL_Persistent addFirst(AVL_Persistent t, AVL_Persistent v) {
			if (t == null) return v;
			t = shallowCopy(t);
			t.l = addFirst(t.l, v);
			return balance(t);
		}
		
		public static
		AVL_Persistent addLast(AVL_Persistent t, AVL_Persistent v) {
			if (t == null) return v;
			t = shallowCopy(t);
			t.r = addLast(t.r, v);
			return balance(t);
		}
		
		public static
		AVL_Persistent peekFirst(AVL_Persistent t) {
			while (t.l != null) t = t.l;
			return t;
		}
		
		public static
		AVL_Persistent removeFirst(AVL_Persistent t) {
			if (t.l == null) return shallowCopy(t.r);
			t = shallowCopy(t);
			t.l = removeFirst(t.l);
			return balance(t);
		}
		
		public static
		AVL_Persistent peekLast(AVL_Persistent t) {
			while (t.r != null) t = t.r;
			return t;
		}
		
		public static
		AVL_Persistent removeLast(AVL_Persistent t) {
			if (t.r == null) return shallowCopy(t.l);
			t = shallowCopy(t);
			t.r = removeLast(t.r);
			return balance(t);
		}
		
		private static
		AVL_Persistent join(AVL_Persistent l, AVL_Persistent v, AVL_Persistent r) {
			if (l == null) { return addFirst(r, v); }
			if (r == null) { return addLast(l, v); }
			
			int hl = height(l);
			int hr = height(r);
			
			if (hl > hr + 2) {
				l = shallowCopy(l);
				l.r = join(l.r, v, r);
				return balance(l);
			}
			
			if (hr > hl + 2) {
				r = shallowCopy(r);
				r.l = join(l, v, r.l);
				return balance(r);
			}

			v.l = l;
			v.r = r;
			v.update();
			return v;
		}
		
		// concat
		public static
		AVL_Persistent merge(AVL_Persistent l, AVL_Persistent r) {
			if (l == null || r == null) return l == null ? r : l;
			AVL_Persistent v = shallowCopy(peekFirst(r));
			return join(l, v, removeFirst(r));
		}
		
		// [0, k) [k, n)
		public static
		Pair<AVL_Persistent, AVL_Persistent> split(AVL_Persistent n, int k) {
			if (n == null) return new Pair<>(null, null);
			n = shallowCopy(n);
			AVL_Persistent l = n.l;
			AVL_Persistent r = n.r;
			n.l = n.r = null;
			n.update();
			int sizeL = size(l);
			if (k < sizeL) {
				Pair<AVL_Persistent, AVL_Persistent> p = split(l, k);
				p.second = join(p.second, n, r);
				return p;
			} else if (k > sizeL) {
				Pair<AVL_Persistent, AVL_Persistent> p = split(r, k - sizeL - 1);
				p.first = join(l, n, p.first);
				return p;
			} else {
				return new Pair<>(l, addFirst(r, n));
			}
		}

		public static
		AVL_Persistent insert(AVL_Persistent t, int k, byte v) {
			Pair<AVL_Persistent, AVL_Persistent> p = split(t, k);
			return join(p.first, new AVL_Persistent(v), p.second);
		}

		public static
		AVL_Persistent erase(AVL_Persistent t, int k) {
			Pair<AVL_Persistent, AVL_Persistent> p = split(t, k);
			return merge(p.first, removeFirst(p.second));
		}
	}
	
	static class Pair<T1, T2> {
		public T1 first;
		public T2 second;
		
		public Pair(final T1 first, final T2 second) {
			this.first = first;
			this.second = second;
		}
	}

	/// TEMPLATE
	static int gcd(int n, int r) { return r == 0 ? n : gcd(r, n%r); }
	static long gcd(long n, long r) { return r == 0 ? n : gcd(r, n%r); }
	
	static <T> void swap(T[] x, int i, int j) { T t = x[i]; x[i] = x[j]; x[j] = t; }
	static void swap(int[] x, int i, int j) { int t = x[i]; x[i] = x[j]; x[j] = t; }

	void printArrayLn(int[] xs) { for(int i = 0; i < xs.length; i++) io.out.print(xs[i] + (i==xs.length-1?"\n":" ")); }
	void printArrayLn(long[] xs) { for(int i = 0; i < xs.length; i++) io.out.print(xs[i] + (i==xs.length-1?"\n":" ")); }
	
	static void dump(Object... o) { System.err.println(Arrays.deepToString(o)); } 
	
	void main() throws IOException {
		//		IOFast.setFileIO("rle-size.in", "rle-size.out");
		try { run(); }
		catch (EndOfFileRuntimeException e) { }
		io.out.flush();
	}
	public static void main(String[] args) throws IOException { new Main().main(); }
	
	static class EndOfFileRuntimeException extends RuntimeException {
		private static final long serialVersionUID = -8565341110209207657L; }

	static
	public class IOFast {
		private BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		private PrintWriter out = new PrintWriter(System.out);

		void setFileIn(String ins) throws IOException { in.close(); in = new BufferedReader(new FileReader(ins)); }
		void setFileOut(String outs) throws IOException { out.flush(); out.close(); out = new PrintWriter(new FileWriter(outs)); }
		void setFileIO(String ins, String outs) throws IOException { setFileIn(ins); setFileOut(outs); }

		private static int pos, readLen;
		private static final char[] buffer = new char[1024 * 8];
		private static char[] str = new char[500*8*2];
		private static boolean[] isDigit = new boolean[256];
		private static boolean[] isSpace = new boolean[256];
		private static boolean[] isLineSep = new boolean[256];

		static { for(int i = 0; i < 10; i++) { isDigit['0' + i] = true; } isDigit['-'] = true; isSpace[' '] = isSpace['\r'] = isSpace['\n'] = isSpace['\t'] = true; isLineSep['\r'] = isLineSep['\n'] = true; }
		public int read() throws IOException { if(pos >= readLen) { pos = 0; readLen = in.read(buffer); if(readLen <= 0) { throw new EndOfFileRuntimeException(); } } return buffer[pos++]; }
		public int nextInt() throws IOException { int len = 0; str[len++] = nextChar(); len = reads(len, isSpace); int i = 0; int ret = 0; if(str[0] == '-') { i = 1; } for(; i < len; i++) ret = ret * 10 + str[i] - '0'; if(str[0] == '-') { ret = -ret; } return ret; }
		public long nextLong() throws IOException { int len = 0; str[len++] = nextChar(); len = reads(len, isSpace); int i = 0; long ret = 0; if(str[0] == '-') { i = 1; } for(; i < len; i++) ret = ret * 10 + str[i] - '0'; if(str[0] == '-') { ret = -ret; } return ret; }
		public char nextChar() throws IOException { while(true) { final int c = read(); if(!isSpace[c]) { return (char)c; } } }
		int reads(int len, boolean[] accept) throws IOException { try { while(true) { final int c = read(); if(accept[c]) { break; } if(str.length == len) { char[] rep = new char[str.length * 3 / 2]; System.arraycopy(str, 0, rep, 0, str.length); str = rep; } str[len++] = (char)c; } } catch(EndOfFileRuntimeException e) { ; } return len; }
		int reads(char[] cs, int len, boolean[] accept) throws IOException { try { while(true) { final int c = read(); if(accept[c]) { break; } cs[len++] = (char)c; } } catch(EndOfFileRuntimeException e) { ; } return len; }
		public char[] nextLine() throws IOException { int len = 0; str[len++] = nextChar(); len = reads(len, isLineSep); try { if(str[len-1] == '\r') { len--; read(); } } catch(EndOfFileRuntimeException e) { ; } return Arrays.copyOf(str, len); }
		public String nextString() throws IOException { return new String(next()); }
		public char[] next() throws IOException { int len = 0; str[len++] = nextChar(); len = reads(len, isSpace); return Arrays.copyOf(str, len); }
//		public int next(char[] cs) throws IOException { int len = 0; cs[len++] = nextChar(); len = reads(cs, len, isSpace); return len; }
		public double nextDouble() throws IOException { return Double.parseDouble(nextString()); }
		public long[] nextLongArray(final int n) throws IOException { final long[] res = new long[n]; for(int i = 0; i < n; i++) { res[i] = nextLong(); } return res; }
		public int[] nextIntArray(final int n) throws IOException { final int[] res = new int[n]; for(int i = 0; i < n; i++) { res[i] = nextInt(); } return res; }
		public int[][] nextIntArray2D(final int n, final int k) throws IOException { final int[][] res = new int[n][]; for(int i = 0; i < n; i++) { res[i] = nextIntArray(k); } return res; }
		public int[][] nextIntArray2DWithIndex(final int n, final int k) throws IOException { final int[][] res = new int[n][k+1]; for(int i = 0; i < n; i++) { for(int j = 0; j < k; j++) { res[i][j] = nextInt(); } res[i][k] = i; } return res; }
		public double[] nextDoubleArray(final int n) throws IOException { final double[] res = new double[n]; for(int i = 0; i < n; i++) { res[i] = nextDouble(); } return res; }
	}
}

Submission Info

Judge Result