読者です 読者をやめる 読者になる 読者になる

スライドk番値

building blocks(15th POI)
別にスライドじゃなくても、集合からN個くらい数が入ったり消えたりするときのk番目の値を答えられる
1.まず座標圧縮
2.segtreeでカウントする
3.にぶたんだが,毎回sumを使うとlogが2回かかる.segtreeなんだから配列の値を足していけばNlogNでいける(実装は、kth(int l,int r,int id,int k)でidのk-th numberを探す,とやって再帰)
コード:

#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <cstring>
#include <functional>
#include <cmath>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
#define rep1(i,n) for(int i=1;i<=(n);++i)
#define all(c) (c).begin(),(c).end()
#define fs first
#define sc second
#define pb push_back
#define show(x) cout << #x << " " << x << endl
typedef long long ll;
int p[100000];
const int p2=1<<17;
ll seg[p2*2],sumseg[p2*2];
vector<ll> ash;
ll sum(int a,int b,int l,int r,int k,ll* seg){
	if(r<=a||b<=l) return 0;
	if(a<=l&&r<=b) return seg[k];
	return sum(a,b,l,(l+r)/2,k*2+1,seg)+sum(a,b,(l+r)/2,r,k*2+2,seg);
}
void add(int x,int v,ll* seg){
	while(true){
		seg[x]+=v;
		if(x==0) break;
		x=(x-1)/2;
	}
}
int kth(int l,int r,int id,int k){
	if(l+1==r) return l;
	if(seg[2*id+1]>=k) return kth(l,(l+r)/2,id*2+1,k);
	else return kth((l+r)/2,r,id*2+2,k-seg[2*id+1]);
}
int main(){
	int n,k;
	cin>>n>>k;
	ll mn=1e18,id=-1,mid=-1;
	rep(i,n) scanf("%d",p+i);
	rep(i,n) ash.pb(p[i]);
	sort(all(ash));
	ash.erase(unique(all(ash)),ash.end());
	rep(i,n) p[i]=lower_bound(all(ash),p[i])-ash.begin();
	rep(i,n){
		add(p2-1+p[i],1,seg);
		add(p2-1+p[i],ash[p[i]],sumseg);
		if(i>=k){
			add(p2-1+p[i-k],-1,seg);
			add(p2-1+p[i-k],-ash[p[i-k]],sumseg);
		}
		if(i>=k-1){
			int m=kth(0,p2,0,(k+1)/2);
			ll val=0;
			val+=sum(m,p2,0,p2,0,sumseg)-sum(m,p2,0,p2,0,seg)*ash[m];
			val+=sum(0,m,0,p2,0,seg)*ash[m]-sum(0,m,0,p2,0,sumseg);
			if(val<mn){
				mn=val;
				id=i-(k-1),mid=ash[m];
			}
		}
	}
	cout<<mn<<endl;
	rep(i,n){
		if(id<=i&&i<id+k) printf("%d\n",mid);
		else printf("%d\n",ash[p[i]]);
	}
}