Sliding Window Inversions

1#include<bits/stdc++.h>
2using namespace std;
3#define int long long
4constexpr int MAXA=1e9;
5struct node{
6  int l,r,m,v;
7  node *lf,*rg;
8  node(int _l,int _r):l(_l),r(_r),m((_l+_r)>>1),v(0){
9    lf=nullptr,rg=nullptr;
10  }
11  void upd(int x,int d){
12    if(l==r){
13      v+=d;
14      return;
15    }
16    if(x<=m){ if(!lf) lf=new node(l,m);
17    }else if(!rg) rg=new node(m+1,r);
18    (x<=m?lf:rg)->upd(x,d);
19    v=(lf?lf->v:0)+(rg?rg->v:0);
20  }
21  int qry(int x,int y){
22    if(x<=l && r<=y) return v;
23    if(x>r || y<l) return 0;
24    return (lf?lf->qry(x,y):0)+(rg?rg->qry(x,y):0);
25  }
26}*root;
27signed main(){
28  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
29  int n,k; cin>>n>>k;
30  int a[n]; for(int i=0;i<n;++i)
31    cin>>a[i];
32  root=new node(1,MAXA);
33  int res=0;
34  for(int i=0;i<n;++i){
35    res+=root->qry(a[i]+1,MAXA);
36    root->upd(a[i],1);
37    if(i>=k) res-=root->qry(1,a[i-k]-1),root->upd(a[i-k],-1);
38    if(i>=k-1) cout<<res<<" ";
39  }
40  cout<<'\n';
41  return 0;
42}