スライド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]]); } }