E. Monsters (hard version)

Monsters (hard version)"/>

E. Monsters (hard version)

只做记录，不是题解

离开集训队好长时间了，也很长时间没有碰这些代码了，最近觉得码力掉了很多，决定操练起来。
ps 这bug调的整个人裂开，一瓶酒一包烟，一个算法写一天。
这调试的代码成功让他上了个百行，炸裂，感觉有一次可以解的算法，懒得想了，线段树+树状数组你俩辛苦下搁这磨吧。

#include<bits/stdc++.h>
using namespace std;const int N=2e5+10;
int tree[N];
int a[N],high[N];
int b[N];
int Step[N];int se_Tr_se;int segement_tree[N<<2];
void update(int l,int r,int node,int x,int y){int mid=l+r>>1;if(l==r) {segement_tree[node]=y;return ;}if(x>mid) update(mid+1,r,(node<<1)+1,x,y);else update(l,mid,node<<1,x,y);if(Step[segement_tree[node<<1]]>Step[segement_tree[(node<<1)+1]]){segement_tree[node]=segement_tree[node<<1];}else{segement_tree[node]=segement_tree[(node<<1)+1];}
}
int query(int l,int r,int node,int L,int R){if(l==L&&r==R) return segement_tree[node];int mid=l+r>>1;if(L>mid) return query(mid+1,r,(node<<1)+1,L,R);if(R<=mid) return query(l,mid,node<<1,L,R);int lidx=query(l,mid,node<<1,L,mid);int ridx=query(mid+1,r,(node<<1)+1,mid+1,R);if(Step[lidx]>Step[ridx]) return lidx;else return ridx;
}
int swap(int st){// cout<<st<<endl;// for(int i=1;i<=st;i++){//     cout<<query(1,se_Tr_se,1,i,i)<<" ";// }puts("");// cout<<query(1,se_Tr_se,1,1,st)<<endl;int ans=0;int tmp;// int l=1,r=st,mid=l+r>>1;// while(l<r){//     if(query(1,se_Tr_se,1,1,mid)>st) r=mid;//     else l=mid+1;//     mid=l+r>>1;// }int idx=query(1,se_Tr_se,1,1,st);tmp=Step[idx];if(tmp>st){ans=tmp-st;Step[idx]=st;update(1,se_Tr_se,1,idx,idx);ans+=swap(tmp);}return ans;
}int lowbit(int x){return x&-x;
}
void add(int x,int y,int len){while(x<=len){tree[x]+=y;x+=lowbit(x);}
}
int query(int x){int ans=0;while(x){ans+=tree[x];x-=lowbit(x);}return ans;
}bool cmp(int x,int y){        if(a[x] == a[y]) return x<y;return a[x]<a[y];
}
bool check(int l,int r){return query(r)-query(l-1) == r-l+1;
}
long long in_step(long long ans,int h,int &num,int tree_se){if(!Step[h]){Step[h]=h;update(1,se_Tr_se,1,h,h);add(h,1,tree_se);num++;ans+=h-1-query(h-1);ans-=num-query(h);}else{ans-=Step[h]-h;int st=Step[h];Step[h]=h;update(1,se_Tr_se,1,h,h);int l=1,r=h,mid=l+r>>1;while(l<r){if(check(mid,h)) r=mid-1;else l=mid;mid=l+r+1>>1;}if(!Step[l]){Step[l]=st;update(1,se_Tr_se,1,l,l);add(l,1,tree_se);num++;ans+=st-l;ans+=l-1-query(l-1);ans-=num-query(l);}else ans-=swap(st);}return ans;
}
void init(int size){se_Tr_se=size;for(int i=1;i<=size;i++){tree[i]=0;Step[i]=0;update(1,se_Tr_se,1,i,i);}
}
void solve(){int n,use=0;scanf("%d",&n);init(n);for(int i=1;i<=n;i++){scanf("%d",a+i);b[i]=i;}sort(b+1,b+n+1,cmp);int step = 0;for(int i=1;i<=n;i++){if(a[b[i]]>step) step++;high[b[i]]=step;}// for(int i=1;i<=n;i++){//     cout<<high[i]<<' ';// }puts("");long long ans=0;for(int i=1;i<=n;i++){// cout<<high[i]<<' '<<a[i]<<endl;ans+=a[i]-high[i];ans=in_step(ans,high[i],use,n);// for(int j=1;j<=n;j++){//     cout<<Step[j]<<' ';// }cout<<endl;// for(int j=1;j<=n;j++){//     cout<<tree[j]<<' ';// }cout<<endl;printf("%lld ",ans);//cout<<endl;cout<<endl;}puts("");
}
int main(){int t;cin >> t;while(t--)solve();
}