M_sea

洛谷2617 Dynamic Rankings
LuoguBZOJ(权限题)分析半个整体二分的板子。和K-th Number只差了一个单点赋值。考虑把单点赋值拆成...
扫描右侧二维码阅读全文
21
2018/12

洛谷2617 Dynamic Rankings

Luogu

BZOJ(权限题)

分析

半个整体二分的板子。和K-th Number只差了一个单点赋值。

考虑把单点赋值拆成减掉原来的数和加上新的数两部分,这样子就可以做了。

细节见代码。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=300000+10;

struct query { int x,y,k,id; } q[MAXN],lq[MAXN],rq[MAXN];
int n,m,t;
int a[MAXN],ans[MAXN];

int c[MAXN];
#define lowbit(x) (x&-x)
inline void add(int x,int y) { while (x<=n) c[x]+=y,x+=lowbit(x); }
inline int sum(int x) { int y=0; while (x) y+=c[x],x^=lowbit(x); return y; }

inline void solve(int lval,int rval,int st,int ed) {
    if (st>ed) return;
    if (lval==rval) {
        for (re int i=st;i<=ed;++i)
            if (q[i].id) ans[q[i].id]=lval;
        return;
    }
    int mid=(lval+rval)>>1,lt=0,rt=0;
    for (re int i=st;i<=ed;++i) {
        if (!q[i].id) { //修改
            if (q[i].y<=mid) add(q[i].x,q[i].k),lq[++lt]=q[i];
            else rq[++rt]=q[i];
        } else { //查询
            int cnt=sum(q[i].y)-sum(q[i].x-1);
            if (cnt>=q[i].k) lq[++lt]=q[i];
            else q[i].k-=cnt,rq[++rt]=q[i];
        }
    }
    for (re int i=ed;i>=st;--i)
        if (!q[i].id&&q[i].y<=mid) add(q[i].x,-q[i].k);
    for (re int i=1;i<=lt;++i) q[st+i-1]=lq[i];
    for (re int i=1;i<=rt;++i) q[st+lt+i-1]=rq[i];
    solve(lval,mid,st,st+lt-1); solve(mid+1,rval,st+lt,ed);
}

int main() {
    n=read(),m=read(); int Q=0;
    for (re int i=1;i<=n;++i)
        a[i]=read(),q[++t]=(query){i,a[i],1,0};
    for (re int i=1;i<=m;++i) {
        char op[2]; scanf("%s",op);
        if (op[0]=='Q') {
            int l=read(),r=read(),k=read();
            q[++t]=(query){l,r,k,++Q};
        } else {
            int x=read(),y=read();
            q[++t]=(query){x,a[x],-1,0};
            q[++t]=(query){x,y,1,0};
            a[x]=y;
        }
    }
    solve(0,1e9,1,t);
    for (re int i=1;i<=Q;++i) printf("%d\n",ans[i]);
    return 0;
}
最后修改:2019 年 02 月 08 日 10 : 27 PM

发表评论