luogu P2617 Dynamic Rankings

题目链接

带修改的区间第k小

整体二分练习题

#include <iostream>
#include <algorithm>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define LL long long
#define pii pair<int,int>
#define SZ(x) (int)x.size()
#define all(x) x.begin(),x.end()

using namespace std;

LL gcd(LL a, LL b) {return b ? gcd(b, a % b) : a;}
LL lcm(LL a, LL b) {return a / gcd(a, b) * b;}
LL powmod(LL a, LL b, LL MOD) {LL ans = 1; while (b) {if (b % 2)ans = ans * a % MOD; a = a * a % MOD; b /= 2;} return ans;}
const int N = 5e5 + 3;
const LL mod = 1e9 + 7;
int n,m,cnt,a[N];
LL ans[N];
struct uzi{
    int o,l,r;
    LL k;
    int pos;
    uzi(){}
    uzi(int a,int b,int c,LL d,int e):o(a),l(b),r(c),k(d),pos(e){};
}p[N],q1[N],q2[N];
int t[N];
void add(int p,int d){
    for(;p<N;p+=p&-p)t[p]+=d;
}
int get(int p){
    int ans=0;
    for(;p;p-=p&-p)ans+=t[p];
    return ans;
}
void solve(LL x,LL y,int l,int r){
    if(l>r||x>y)return ;
    if(x==y){
       for(int i=l;i<=r;i++)if(p[i].o==2)ans[p[i].pos]=x;//out<<p[i].l<<' '<<p[i].r<<' '<<p[i].pos<<endl;cout<<endl;
       return ;
    }
    LL mid=x+y>>1;
    int c=0,d=0;
    for(int i=l;i<=r;i++){
        if(p[i].o==1){
            if(p[i].k<=mid)q1[++c]=p[i],add(p[i].l,p[i].r);
            else q2[++d]=p[i];
        }else{
            int x=get(p[i].r)-get(p[i].l-1);
            if(x>=p[i].k)q1[++c]=p[i];
            else p[i].k-=x,q2[++d]=p[i];
        }
    }
    for(int i=l;i<=r;i++)if(p[i].o==1&&p[i].k<=mid)add(p[i].l,-p[i].r);
    for(int i=l;i<=l+c-1;i++)p[i]=q1[i-l+1];
    for(int i=l+c;i<=r;i++)p[i]=q2[i-l-c+1];
    solve(x,mid,l,l+c-1);
    solve(mid+1,y,l+c,r);
}
int c[N];
char T[N];
int main() {
	ios::sync_with_stdio( false);
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i],p[++cnt]=uzi(1,i,1,a[i],i);
	for(int i=1;i<=m;i++){
	    int l,r,k;
	    char o;
	    cin>>o;
	    T[i]=o;
	    if(o=='Q'){
            cin>>l>>r>>k;
            p[++cnt]=uzi(2,l,r,k,i);
	    }else{
	        cin>>l>>r;
	        p[++cnt]=uzi(1,l,-1,a[l],l);
	        p[++cnt]=uzi{1,l,1,r,l};
	        a[l]=r;
	    }

	}
	solve(-2e9,2e9,1,cnt);
	for(int i=1;i<=m;i++)if(T[i]=='Q')cout<<ans[i]<<'\n';
    return 0;
}