## AtCoder ABC 342 G - Retroactive Range Chmax

[<<回主頁](https://hackmd.io/@r1cky/Sk2hKzga6)

### 解題想法

我們可以開一棵線段樹來維護區間，區間操作單點查詢，然後取消操作的話，我們可以把線段樹的節點改成一個 pq，這樣每次查詢我們從 pq 裡面拿最大的值出來，如果發現他是被移除的就繼續從 pq 拿，做一次操作的上界是 $O(logN)$ (以下假設 $N=Q$)，然後線段樹一次最多動到 $O(logN)$ 的節點，所以加入操作是 $O(log^2N)$，刪除的話用陣列維護可以弄到 $O(1)$ (實際的刪除會被挪動到查詢的時候)。

注意一次從 pq 整體拿出東西，有可能一次拿需要拿很多，但整體會均攤，不會超過 $O(Nlog^2N)$。

總時間複雜度 $O(Nlog^2N)$，但實際上不會那麼大，不會跑滿。

### Code

Java =

import java.util.*;
import java.time.*;
import java.io.*;
import java.math.*;
public class Main{
	public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
	public static long ret,cnt,ansl;
	public static int reti,rd,n,m,ans;
	public static String[] in;
	public static String in1="";
	public static boolean neg,b1,b2,b3;
	public static final int mod=998244353,mox=998244352,mod2=1_000_000_007,ma=200015;
	public static Useful us=new Useful(mod2);
	public static int[] A=new int[ma];
	public static int[] B=new int[ma];
	public static int[] C=new int[ma];
	public static int[] D=new int[ma];
	public static long[] Al=new long[ma];
	public static long[] Bl=new long[ma];
	public static ArrayList<ArrayList<Integer>> E=new ArrayList<>();
	public static ArrayList<ArrayList<Integer>> E=new ArrayList<>();
	public static void main(String[] args) throws Exception{
		final int n=readint();
		int op,l,r,x;
		Node tree=build(1,n);
		for(int i=1;i<=n;i++) {
			A[i]=readint();
		}
		final int q=readint();
		boolean[] rm=new boolean[ma];
		for(int i=1;i<=q;i++) {
			op=readint();
			if(op==1) {
				l=readint();
				r=readint();
				x=readint();
				add(tree,1,n,l,r,i,x);
			}
			if(op==2) {
				x=readint();
				rm[x]=true;
			}
			if(op==3) {
				x=readint();
				bw.write(Math.max(A[x], query(tree,rm,1,n,x))+"\n");
			}
		}
		bw.flush();
	}
	
	public static Node build(int l,int r) {
		Node now=new Node();
		if(l!=r) {
			int mid=(l+r)>>1;
			now.l=build(l,mid);
			now.r=build(mid+1,r);
		}
		return now;
	}
	
	public static void add(Node x,int l,int r,int ql,int qr,int op,int v) {
		if(r<ql||l>qr) {
			return;
		}
		if(ql<=l&&r<=qr) {
			x.modify(op,v);
			return;
		}
		int mid=(l+r)>>1;
		add(x.l,l,mid,ql,qr,op,v);
		add(x.r,mid+1,r,ql,qr,op,v);
	}
	
	public static int query(Node x,boolean[] rm,int l,int r,int q) {
		if(l==r)return x.get(rm);
		int mid=(l+r)>>1;
		if(q<=mid) {
			return Math.max(x.get(rm), query(x.l,rm,l,mid,q));
		}
		return Math.max(x.get(rm), query(x.r,rm,mid+1,r,q));
	}
/*


 */
	//fast io
	public static int readint() throws Exception{
		reti=0;
		neg=false;
		while(rd<48||rd>57) {
			rd=br.read();
			if(rd=='-') {
				neg=true;
			}
//			if(rd<0) {
//				return -1; //EOF
//			}
		}
		while(rd>47&&rd<58) {
			reti*=10;
			reti+=(rd&15);
			rd=br.read();
		}
		if(neg)reti*=-1;
		return reti;
	}
	public static long readlong() throws Exception{
		ret=0;
		neg=false;
		while(rd<48||rd>57) {
			rd=br.read();
			if(rd=='-') {
				neg=true;
			}
		}
		while(rd>47&&rd<58) {
			ret*=10;
			ret+=(rd&15);
			rd=br.read();
		}
		if(neg)ret*=-1;
		return ret;
	}
	//fast typing
	public static int pint(String in) {
		return Integer.parseInt(in);
	}
	public static long plong(String in) {
		return Long.parseLong(in);
	}
	public static void outn() {
		System.out.println();
	}
	public static void outn(char in) {
		System.out.println(in);
	}
	public static void outn(long in) {
		System.out.println(in);
	}
	public static void outn(double in) {
		System.out.println(in);
	}
	public static void outn(boolean in) {
		System.out.println(in);
	}
	public static void outn(String in) {
		System.out.println(in);
	}
	public static void outn(Object in) {
		System.out.println(in);
	}
	public static void out(char in) {
		System.out.print(in);
	}
	public static void out(long in) {
		System.out.print(in);
	}
	public static void out(double in) {
		System.out.print(in);
	}
	public static void out(boolean in) {
		System.out.print(in);
	}
	public static void out(String in) {
		System.out.print(in);
	}
	public static void out(Object in) {
		System.out.print(in);
	}
	public static void fl() {
		System.out.flush();
	}
	public static String[] res() throws IOException{
		return br.readLine().split(" ");
	}
	public static String re() throws IOException{
		return br.readLine().split(" ")[0];
	}
}

/*

 */
 
/*
 
 */

class Node {
	Node l, r;
	Pii u;
	PriorityQueue<Pii> pq=new PriorityQueue<>(new Comparator<Pii>() {
		public int compare(Pii f,Pii s) {
			return s.y-f.y;
		}
	});
	Node(){	
	}
	
	int get(boolean[] rm) {
		while(!pq.isEmpty()) {
			u=pq.poll();
			if(!rm[u.x]) {
				pq.offer(u);
				return u.y;
			}
		}
		return 0;
	}
	
	void modify(int op,int v) {
		pq.offer(new Pii(op,v));
	}
	
}
class ooo{
	int x,y,z;
	public String err() {
		return x+" "+y+" "+z;
	}
	ooo(int x1,int y1,int z1){
		x=x1;
		y=y1;
		z=z1;
	}
	
}

class Pii{
	int x,y;
	Pii(int a,int b){
		x=a;
		y=b;
	}
	public String err() {
		return x+" "+y;
	}
	@Override
    public boolean equals(Object o) {
        if (this==o) return true;
        if (!(o instanceof Pii)) return false;
        Pii key = (Pii) o;
        return x==key.x&&y==key.y;
    }

    @Override
    public int hashCode() {
        long result=x;
        result=31*result+y;
        return (int)(result%998244353);
    }
}

class Pll{
	long x,y;
	Pll(long a,long b){
		x=a;
		y=b;
	}
	public String err() {
		return x+" "+y;
	}
	@Override
    public boolean equals(Object o) {
        if (this==o) return true;
        if (!(o instanceof Pll)) return false;
        Pll key = (Pll) o;
        return x==key.x&&y==key.y;
    }

    @Override
    public int hashCode() {
        long result=x;
        result=31*result+y;
        return (int)(result%998244353);
    }
}


class Useful{
	long mod;
	Useful(long m){mod=m;}
	void al(ArrayList<ArrayList<Integer>> a,int n){for(int i=0;i<n;i++) {a.add(new ArrayList<Integer>());}}
	void arr(int[] a,int init) {for(int i=0;i<a.length;i++) {a[i]=init;}}
	void arr(long[] a,long init) {for(int i=0;i<a.length;i++) {a[i]=init;}}
	void arr(int[][] a,int init) {for(int i=0;i<a.length;i++) {for(int j=0;j<a[i].length;j++) {a[i][j]=init;}}}
	void arr(long[][] a,long init) {for(int i=0;i<a.length;i++) {for(int j=0;j<a[i].length;j++) {a[i][j]=init;}}}
	void arr(int[][][] a,int init) {for(int i=0;i<a.length;i++) {for(int j=0;j<a[i].length;j++) {for(int k=0;k<a[i][j].length;k++) {a[i][j][k]=init;}}}}
	void arr(long[][][] a,long init) {for(int i=0;i<a.length;i++) {for(int j=0;j<a[i].length;j++) {for(int k=0;k<a[i][j].length;k++) {a[i][j][k]=init;}}}}
	void arr(int[][][][] a,int init) {for(int i=0;i<a.length;i++) {for(int j=0;j<a[i].length;j++) {for(int k=0;k<a[i][j].length;k++) {Arrays.fill(a[i][j][k],init);}}}}
	void arr(long[][][][] a,long init) {for(int i=0;i<a.length;i++) {for(int j=0;j<a[i].length;j++) {for(int k=0;k<a[i][j].length;k++) {Arrays.fill(a[i][j][k],init);}}}}
	long fastn(long x,long pw) {
		if(pw==1)return x;
		long h=fastn(x,pw>>1);
		if((pw&1)==0) {
			return h*h;
		}
		return h*h*x;
	}
	long fast(long x,long pw) {
		if(x==0)return 1;
		if(pw<=0)return 1;
		if(pw==1)return x;
		long h=fast(x,pw>>1);
		if((pw&1)==0) {
			return h*h%mod;
		}
		return h*h%mod*x%mod;
	}
	long fast(long x,long pw,long mod) {
		if(pw<=0)return 1;
		if(pw==1)return x;
		long h=fast(x,pw>>1,mod);
		if((pw&1)==0) {
			return h*h%mod;
		}
		return h*h%mod*x%mod;
	}
	long[][] mul(long[][] a,long[][] b){
		long[][] c=new long[a.length][b[0].length];
		for(int i=0;i<a.length;i++) {
			for(int j=0;j<b[0].length;j++) {
				for(int k=0;k<a[0].length;k++) {
					c[i][j]+=a[i][k]*b[k][j];
					c[i][j]%=mod;
				}
			}
		}
		return c;
	}
	long[][] mul(long[][] a,long[][] b,long mod){
		long[][] c=new long[a.length][b[0].length];
		for(int i=0;i<a.length;i++) {
			for(int j=0;j<b[0].length;j++) {
				for(int k=0;k<a[0].length;k++) {
					c[i][j]+=a[i][k]*b[k][j];
					c[i][j]%=mod;
				}
			}
		}
		return c;
	}
	long[][] fast(long[][] x,long pw){
		if(pw==1)return x;
		long[][] h=fast(x,pw>>1);
		if((pw&1)==0) {
			return mul(h,h);
		}
		else {
			return mul(mul(h,h),x);
		}
	}
	long[][] fast(long[][] x,long pw,long mod){
		if(pw==1)return x;
		long[][] h=fast(x,pw>>1,mod);
		if((pw&1)==0) {
			return mul(h,h,mod);
		}
		else {
			return mul(mul(h,h,mod),x,mod);
		}
	}
	int gcd(int a,int b) {
		if(a==0)return b;
		if(b==0)return a;
		return gcd(b,a%b);
	}
	long gcd(long a,long b) {
		if(a==0)return b;
		if(b==0)return a;
		return gcd(b,a%b);
	}
	long lcm(long a, long b){
	    return a*(b/gcd(a,b));
	}
	double log2(long x) {
		return (Math.log(x)/Math.log(2));
	}
	double logx(long x,long y) {
		return (Math.log(y)/Math.log(x));
	}
}