2024江苏省赛E. Divide

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

1. #include<bits/stdc++.h>
2. using namespace std;
3. using i64 = long long;
4. using i128 = __int128;
6. constexpr int maxn = 1e5+10;
7. struct ty{
8.     int l,r,sum;
9. }hjt[maxn*280];
10. int cnt,root[maxn];
11. int n,q,a[maxn],c[maxn];
13. inline void insert(int l,int r,int pre,int &now,int p){
14.     hjt[++cnt] = hjt[pre];
15.     now = cnt;
16.     hjt[now].sum++;
17.     if(l==r) return;
18.     int mid = (l+r)>>1;
19.     if(p<=mid) insert(l,mid,hjt[pre].l,hjt[now].l,p);
20.     else insert(mid+1,r,hjt[pre].r,hjt[now].r,p);
21. }
23. inline int query(int l,int r,int L,int R,int k){
24.     if(l==r) return l;
25.     int mid = (l+r)>>1;
26.     int tmp = hjt[hjt[R].l].sum-hjt[hjt[L].l].sum;//会在这里减掉1-[l-1]版本的影响
27.     if(k<=tmp) return query(l,mid,hjt[L].l,hjt[R].l,k);
28.     else return query(mid+1,r,hjt[L].r,hjt[R].r,k-tmp);
29. }
32. signed main(){
33.     ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
34.     cin>>n>>q;
35.     for(int i = 1;i<=n;++i){
36.         cin>>a[i];
37.         c[i]=c[i-1];
38.         insert(0,1e5,root[i-1],root[i],a[i]);
39.         ++c[i];a[i]>>=1;
40.         while(a[i]){
41.             insert(0,1e5,root[i],root[i],a[i]);
42.             a[i]>>=1;
43.             c[i]++;
44.         }
45.     }
46.     while(q--){
47.         int l,r,k;
48.         cin>>l>>r>>k;
49.         if(k>=c[r]-c[l-1]) cout<<"0\n";
50.         else cout<<query(0,1e5,root[l-1],root[r],c[r]-c[l-1]-k)<<"\n";
51.     }
52.     return 0;
53. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

继续阅读请点击广告