Submission #2118813

---

Source Code Expand

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class TEST{
	static void Main(){
		Sol mySol =new Sol();
		mySol.Solve();
	}
}

class Sol{
	public void Solve(){
		
		int NN = 2 * N;
		long suma = 0, sumb = 0;
		int cnta = 0, cntb = 0;
		var STa = new SegTreeMin(NN);
		var STb = new SegTreeMin(NN);
		
		for(int i=0;i<NN;i++){
			if(i == 0 || i == NN - 1 || A[i] >= B[i]){
				suma += A[i];
				cnta++;
				if(!(i == 0 || i == NN - 1)) STa.Update(i,A[i] - B[i]);
			} else {
				sumb += B[i];
				cntb++;
				STb.Update(i,B[i] - A[i]);
			}
		}
		
		long[] ans = new long[Q];
		for(int q=0;q<Q;q++){
			int p = P[q];
			long x = X[q];
			long y = Y[q];
			
			STa.Disable(p);
			STb.Disable(p);
			if(p == 0 || p == NN - 1 || A[p] >= B[p]){
				suma -= A[p];
				cnta--;
			} else {
				sumb -= B[p];
				cntb--;
			}
			
			A[p] = x;
			B[p] = y;
			if(p == 0 || p == NN - 1 || A[p] >= B[p]){
				suma += A[p];
				cnta++;
				if(!(p == 0 || p == NN - 1)) STa.Update(p,A[p] - B[p]);
			} else {
				sumb += B[p];
				cntb++;
				STb.Update(p,B[p] - A[p]);
			}
			
			long maxSum = suma + sumb;
			if(cnta % 2 != 0){
				maxSum -= Math.Min(STa.QueryMin(0,NN),STb.QueryMin(0,NN));
			}
			
			ans[q] = maxSum;
		}
		
		Console.WriteLine(String.Join("\n",ans));
		
	}
	int N,Q;
	long[] A,B;
	long[] X,Y;
	int[] P;
	public Sol(){
		
		var d = ria();
		N = d[0]; Q = d[1];
		A = rla();
		B = rla();
		P = new int[Q];
		X = new long[Q];
		Y = new long[Q];
		for(int i=0;i<Q;i++){
			d = ria();
			P[i] = d[0] - 1;
			X[i] = d[1];
			Y[i] = d[2];
		}
		
		
	}

	static String rs(){return Console.ReadLine();}
	static int ri(){return int.Parse(Console.ReadLine());}
	static long rl(){return long.Parse(Console.ReadLine());}
	static double rd(){return double.Parse(Console.ReadLine());}
	static String[] rsa(char sep=' '){return Console.ReadLine().Split(sep);}
	static int[] ria(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>int.Parse(e));}
	static long[] rla(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>long.Parse(e));}
	static double[] rda(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>double.Parse(e));}
}


class SegTreeMin{
	//segment Tree 
	// 0-origin
	protected long[] Data;	
	protected long Inf;	
	protected int N;		
	protected int n;		
	
	public SegTreeMin(int n_){
		N = n_; Inf = (long)1e18;
		n = 1;
		while(n < n_) n *= 2;
		Data = new long[2 * n - 1];
		for(int i=0; i < 2 * n - 1; i++) Data[i] = Inf;
	}
	
	//	   0
	//	 1   2
	//	3 4 5 6
	public void Update(int k,long a){
		k+=n-1;	
		Data[k]=a;
		while(k>0){
			k=(k-1)/2;
			Data[k]=Math.Min(Data[k*2+1],Data[k*2+2]);
		}
	}
	
	
	public long QueryMin(int a, int b){
		return Query(a, b, 0, 0, n);
	}
	//RMQ; [a,b)
	public long Query(int a,int b,int k,int l,int r){
		if(r <= a || b <= l) return Inf;
		if(a <= l && r <= b) return Data[k];
		
		var vl = Query(a, b, k * 2 + 1, l, (l + r) / 2);
		var vr = Query(a ,b, k * 2 + 2, (l + r) / 2, r);
		return Math.Min(vl, vr);
	}
	
	public void Disable(int k){
		Update(k, Inf);
	}
	public bool IsDisabled(int k){
		return Data[k + n - 1] == Inf;
	}
	
	public long Min{
		get{ return Data[0];}
	}
	
	
	public void Dump(){
		Console.WriteLine();
		int h = 0;
		int cnt = 0;
		for(int i=0;i<Data.Length;i++){
			Console.Write("{0} ", Data[i]);
			cnt++;
			if(cnt == 1 << h){
				cnt = 0;
				h++;
				Console.WriteLine();
			}
		}
	}
	
}

Submission Info

Judge Result