bzoj1901: Zju2112 Dynamic Rankings

摘要:
=mp[i-1])mp[++p]=mp[i];m=p;forrt[i]=rt[i-1],insert;//这里直接建主席树就好了for{if{printf;}else{add;a[q[i].x]=q[i].d;add;}}return0;}0
题目链接

bzoj1901: Zju2112 Dynamic Rankings

题解

带修改主席树
只需要在外面套一层BIT
原先的主席树是一串前缀,现在把这个前缀换成bit就是了
建树复杂度是nlog^2n的
对于这题可以只用bit维护修改的内容,开始只需要建常规主席树就好
这样建树的复杂度是nlogn的

代码
#include<cstdio> 
#include<algorithm> 
 
#define ls(x) t[x].lc
#define rs(x) t[x].rc
typedef long long ll;
const int maxn = 20007; 
inline int read() {
     int x = 0,f = 1; 
     char c = getchar(); 
     while(c < '0' || c > '9') c = getchar(); 
     while(c <= '9' && c >= '0')x = x * 10 + c - '0',c = getchar(); 
     return x * f; 
} 
#define lowbit(x) (x & -x) 
int n,Q,m,a[maxn],mp[maxn];  
char s[20];  
struct Que{  
    int type,i,j,k,x,d; 
} q[maxn];  
inline int bin(int v) { 
    int l = 1,r = m ; 
    while(l <= r) { 
        int mid = l + r >> 1;
        if(mp[mid] == v) return mid;
        if(mp[mid] > v) r = mid - 1; 
        else l = mid + 1;   
    } 
    return - 1; 
} 
  
struct node { 
    int lc,rc,w; 
}t[maxn * 100]; 
int sz = 0,root[maxn],rt[maxn]; 
void insert(int &x,int l,int r,int num,int v) { 
    t[++sz] = t[x];x = sz; 
    t[x].w += v; 
    if(l == r) return; 
    int mid = (l + r) >> 1; 
    if(num <= mid) insert(t[x].lc,l,mid,num,v); 
    else insert(t[x].rc,mid + 1,r,num,v); 
} 
void add(int p,int v) { 
    int tmp = bin(a[p]); 
    for(int i = p;i <= n;i += lowbit(i)) insert(root[i],1,m,tmp,v); 
}  
int q1[maxn],t1,q2[maxn],t2; 
int cal() {  
    int sum1 = 0,sum2 = 0; 
    for(int i = 1;i <= t1;i ++) sum1 += t[ls(q1[i])].w; 
    for(int i = 1;i <= t2;i ++) sum2 += t[ls(q2[i])].w; 
    return sum2 - sum1; 
} 
int query(int ql,int qr,int k) {  
    int l = 1,r = m;t1 = t2 = 0; 
    for(int i = ql - 1;i;i -= lowbit(i)) q1[++ t1] = root[i]; 
    for(int i = qr;i;i -= lowbit(i)) q2[++ t2] = root[i]; 
    ql --;
    ql = rt[ql]; qr = rt[qr];
    while(l < r) { 
        int lsiz = cal() + t[ls(qr)].w - t[ls(ql)].w,mid = (l + r) >> 1; 
        if(k <= lsiz) { 
            for(int i = 1;i <= t1;++ i) q1[i] = t[q1[i]].lc; 
            for(int i = 1;i <= t2;++ i) q2[i] = t[q2[i]].lc; 
            ql = ls(ql);qr = ls(qr); 
            r = mid; 
        }else { 
            for(int i = 1;i <= t1;++ i) q1[i] = t[q1[i]].rc; 
            for(int i = 1;i <= t2;++ i) q2[i] = t[q2[i]].rc; 
            ql = rs(ql);qr = rs(qr); 
            l = mid + 1;k -= lsiz ; 
        } 
    } 
    return l; 
} 
int main() { 
    n = read(), Q = read(); 
    char s[10]; 
    for(int i = 1;i <= n;i ++) a[i] = mp[++ m] = read(); 
    for(int i = 1;i <= Q ;i ++) {  
        scanf("%s",s + 1); 
        if(s[1] == 'Q') q[i].type = 0,q[i].i = read(),q[i].j = read(),q[i].k = read(); 
        else q[i].type = 1, q[i].x = read(),q[i].d = mp[++ m] = read(); 
    } 
    std::sort(mp + 1,mp + m + 1); 
    int p = 1; for(int i = 2;i <= m;i ++) if(mp[i] != mp[i - 1]) mp[++ p] = mp[i]; m = p; 
    for(int i = 1;i <= n;i ++) rt[i] = rt[i-1],insert(rt[i],1,m,bin(a[i]),1); //这里直接建主席树就好了 
    for(int i = 1;i <= Q;i ++) {  
        if(q[i].type == 0) {  
            printf("%d
",mp[query(q[i].i,q[i].j,q[i].k)]);  
        } else {  
            add(q[i].x,-1);  
            a[q[i].x] = q[i].d;  
            add(q[i].x,1); 
        } 
    } 
    return 0; 
}  0

免责声明:文章转载自《bzoj1901: Zju2112 Dynamic Rankings》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇C# 之 OpenFileDialog的使用Flask(三)下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

随便看看

windows 常用命令行操作

目录操作˃pwd打印当前工作目录,通过此关键词可以查看当前所处的路径˃cd更改目录,用于多个目录之间的切换具体输入:cd目录名cd目录名/子目录名(可通过此方式到达最底层的目录)cd~(返回home目录)cd..(返回上一级目录)cd../..(返回上两级目录)cd盘符名:(不同盘符间跳转,cd后面跟上路径则可实现精准跳转)˃mkdir创建目录具体输入:mk...

使用Docker构建redis集群

将六个独立的Redis节点关联到主机上的Redis集群中。Redis部落。rb是Redis官方提供的一个ruby脚本,用于构建Redis集群并修改Redis conf将其移动到上部路径/usr/docker_root/redis_Cluster/。受保护模式norequipassa1s2W3l4%Greunbind无法连接到凹坑以构建Redis基本映像。9....

十四、ES开启密码认证

所以我们需要为es head和kibana添加密码认证。4、 为kibana设置密码。1.为kibana配置证书。因为kibana和es之间的连接也需要证书加密通信。mkdir-p/etc/kibana/certscp/etc/selastic search/certs-*/etc/kibana/certs/2.授予kibana主要权限。权限必须为kiban...

neo4j修改密码

输入neo4j提供的可视界面,并输入::serverchange密码。键入原始密码和新密码以修改浏览器。在系统数据库(:usesystem)中,执行以下命令ALTERUSERneo4jSETPASSWORD“mynewpass”:;...

谷歌浏览器中预览海康大华等监控视频的思路与方法

本人近些年来对海康,大华,宇视等视频厂商做过一些视频对接的开发,但始终存在一个问题,在谷歌浏览器中如何进行视频监控的预览。本文将主要解决在谷歌,火狐等非IE浏览器中预览视频监控问题,给广大开发者提供一个思路方法。现在谷歌浏览器中现已不支持ActiveXObject的创建及调用,这是由于chrome浏览器在45版本后不再提供对npapi插件的支持。这种方式基本...

iostat

-pdevice|ALL和-x选项互斥。它们用于显示块设备和系统分区的统计信息。您还可以在-p之后指定设备名称,例如#iostat phda或显示所有设备:#iostat pALL-t输出数据时,打印数据收集时间---等待I/O svctm的平均时间:服务时间,从生成IO请求到完成IO的时间。从源代码中可以看出:--完成I/O需求的平均时间*=util---...