2k小权值和

package tgb.第二章;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class okt2k小权值和 {
	
	static int N=(int) (2e5+7); 
//	static Map<Integer, Integer> S = new HashMap<Integer, Integer>() ;
	static int n,q;
	static int a[] = new int[N];
	static int u[] = new int[N];
	static int v[] = new int[N];
	static int siz[] = new int[N<<2];
	static long F[][] = new long[N<<2][2]; 
	static class pair implements Comparable<pair>{
		int first,second;

		@Override
		public int compareTo(pair o) {
			// TODO Auto-generated method stub
			if(this.first==o.first) return this.second-o.second;
		    return this.first-o.first;
		}
	}
	static pair G[] = new pair[N];
	static Scanner scanner = new Scanner(System.in);
	private static void add(int l,int r,int t,int c){
	    if(l==r){
	        siz[t]=1;
	        F[t][0]=G[c].first;//对排序为2k+1的数求和
	        F[t][1]=0;//对排序为2k的数求和
	        return;
	    }
	    int d=(l+r)>>1;
	    if(c<=d) add(l,d,t<<1,c);
	    else add(d+1,r,t<<1|1,c);
	    siz[t]=siz[t<<1]+siz[t<<1|1];
	    for(int i=0;i<=1;i++)
	        F[t][i]=F[t<<1][i]+F[t<<1|1][(i+siz[t<<1])%2];
	}
	private static void sub(int l,int r,int t,int c){
	    if(l==r){
	        siz[t]=0;
	        F[t][0]=0;
	        F[t][1]=0;
	        return;
	    }
	    int d=(l+r)>>1;
	    if(c<=d) sub(l,d,t<<1,c);
	    else sub(d+1,r,t<<1|1,c);
	    siz[t]=siz[t<<1]+siz[t<<1|1];
	    for(int i=0;i<=1;i++)
	        F[t][i]=F[t<<1][i]+F[t<<1|1][(i+siz[t<<1])%2];
	}
	public static void main(String[] args) {
	        n = scanner.nextInt();
	        q = scanner.nextInt();
		    for(int i=1;i<=n;i++) a[i] = scanner.nextInt();
		    for(int i=1;i<=q;i++) {u[i] = scanner.nextInt();v[i] = scanner.nextInt();}
		    for(int i=n+1;i<=n+q;i++) a[i]=v[i-n];
		    for(int i=1;i<=n+q;i++) {
		    	G[i] = new pair();
		    	G[i].first=a[i];
		    	G[i].second=i;
		    }
		    Arrays.sort(G,1,n+q+1);
		    for(int i=1;i<=n+q;i++) a[G[i].second]=i;
		    for(int i=1;i<=n;i++) add(1,n+q,1,a[i]);
		    for(int i=1;i<=q;i++){
		        sub(1,n+q,1,a[u[i]]);
		        a[u[i]]=a[i+n];
		        add(1,n+q,1,a[u[i]]);
		        System.out.println(F[1][1]);
		    }
	}
	//2 6
	//2 6
	//3 5
}