首页
登录 | 注册

【题解】BZOJ 1901: Zju2112 Dynamic Rankings

题目传送门(权限题)

一道类似的非权限题

题意

N个数的序列,每次修改一个数或者询问区间里的第K小。可以离线。

简要做法

假如要求在线,可以树状数组套个线段树~

但是这题是可以离线的,就可以乱搞整体二分啦~

非常好写好调。(图文无关)

【题解】BZOJ 1901: Zju2112 Dynamic Rankings

细节

  • 可以把一个修改拆成+1和-1两个操作
  • 数组要开到30000左右,如果初始数组也当做操作的话

代码

#include <bits/stdc++.h>
#define TR(x) cerr<<#x<<'='<<x<<endl
using namespace std;
const int MAXN=30005, INF=0x3f3f3f3f;
void rd(int &x){
    x=0; int ch=getchar();
    while(ch<'0'||'9'<ch) ch=getchar();
    while('0'<=ch&&ch<='9') x=x*10+ch-'0', ch=getchar();
}
int N, M, nq;
int A[MAXN], c[MAXN], id[MAXN], q1[MAXN], q2[MAXN], ans[MAXN];
void add(int x, int k){for(;x<=N;x+=x&-x)c[x]+=k;}
int sum(int x){int r=0;for(;x;x-=x&-x)r+=c[x];return r;}
struct Qry{
    int t,a,b,k;
    Qry(int t,int a,int b,int k):t(t),a(a),b(b),k(k){}
    Qry(){}
}Q[MAXN];
void solve(int *a, int n, int l, int r){
    if(!n) return;
    if(l==r){
        for(int i=0; i<n; ++i) ans[a[i]]=l;
        return;
    }
    int mid=(l+r)>>1, n1=0, n2=0;
    for(int i=0; i<n; ++i){
        Qry &q=Q[a[i]];
        if(q.t==0){
            if(q.b<=mid) add(q.a,q.k),q1[n1++]=a[i];
            else q2[n2++]=a[i];
        }else{
            int t=sum(q.b)-sum(q.a-1);
            if(q.k<=t) q1[n1++]=a[i];
            else q.k-=t,q2[n2++]=a[i];
        }
    }
    for(int i=0; i<n; ++i){
        Qry &q=Q[a[i]];
        if(q.t==0&&q.b<=mid) add(q.a,-q.k);
    }
    memcpy(a,q1,sizeof(int)*n1);
    memcpy(a+n1,q2,sizeof(int)*n2);
    solve(a,n1,l,mid);
    solve(a+n1,n2,mid+1,r);
}
int main(){
    rd(N),rd(M);
    for(int i=1; i<=N; ++i) rd(A[i]),Q[nq++]=Qry(0,i,A[i],1);
    for(int i=1; i<=M; ++i){
        char o[3]; scanf("%s",o);
        int a,b,k;
        if(o[0]=='Q'){
            rd(a),rd(b),rd(k);
            Q[nq++]=Qry(1,a,b,k);
        }else{
            rd(a),rd(k);
            Q[nq++]=Qry(0,a,A[a],-1);
            Q[nq++]=Qry(0,a,A[a]=k,1);
        }
    }
    for(int i=0; i<nq; ++i) id[i]=i;
    solve(id,nq,0,INF);
    for(int i=0; i<nq; ++i)if(Q[i].t)printf("%d\n",ans[i]);
    return 0;
}

相关文章

  • 学了很多乱七杂八的东西,但是依然停留在前端,在工作中一直和后端交流,但是不太了解数据库是怎么回事,为了加强学习,准备学习一些关于数据库相关的东西. 说起数据库可能会有很多很多,SQLServer.Oracle.Sybase等等等,还有就是要 ...
  • asp.net core系列 60 Ocelot 构建服务认证示例
    一.概述 在Ocelot中,为了保护下游api资源,用户访问时需要进行认证鉴权,这需要在Ocelot 网关中添加认证服务.添加认证后,ReRoutes路由会进行身份验证,并使用Ocelot的基于声明的功能.在Startup.cs中注册认证服 ...

2019 cecdns.com webmaster#cecdns.com
12 q. 0.077 s.
京ICP备10005923号