logo设计找什么公司_app下载注册推广_seo排名需要多少钱_没广告的视频播放器app

补题链接

题目大意:
每次操作会把区间内最大值除以2，q次询问，问[l,r]操作k次后的结果是什么

分析:
一道主席树的题目,可以先最整个区间一直进行除以2的操作，问区间[l,r]操作后结果，其实就可以转化为求区间第k+1大的结果,反转一下就是求区间第$sum-k-1$小值，这样就是比较裸的主席树了，需要注意的是每次插入操作的时候，需要把数从$a[i]$加入然后除以2，直到为0停止，至于版本的话就是索引$1$到$n$

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using i128 = __int128;constexpr int maxn = 1e5+10;
struct ty{int l,r,sum;
}hjt[maxn*280];
int cnt,root[maxn];
int n,q,a[maxn],c[maxn];inline void insert(int l,int r,int pre,int &now,int p){hjt[++cnt] = hjt[pre];now = cnt;hjt[now].sum++;if(l==r) return;int mid = (l+r)>>1;if(p<=mid) insert(l,mid,hjt[pre].l,hjt[now].l,p);else insert(mid+1,r,hjt[pre].r,hjt[now].r,p);
}inline int query(int l,int r,int L,int R,int k){if(l==r) return l;int mid = (l+r)>>1;int tmp = hjt[hjt[R].l].sum-hjt[hjt[L].l].sum;//会在这里减掉1-[l-1]版本的影响if(k<=tmp) return query(l,mid,hjt[L].l,hjt[R].l,k);else return query(mid+1,r,hjt[L].r,hjt[R].r,k-tmp);
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>q;for(int i = 1;i<=n;++i){cin>>a[i];c[i]=c[i-1];insert(0,1e5,root[i-1],root[i],a[i]);++c[i];a[i]>>=1;while(a[i]){insert(0,1e5,root[i],root[i],a[i]);a[i]>>=1;c[i]++;}}while(q--){int l,r,k;cin>>l>>r>>k;if(k>=c[r]-c[l-1]) cout<<"0\n";else cout<<query(0,1e5,root[l-1],root[r],c[r]-c[l-1]-k)<<"\n";}return 0;
}