首页
登录 | 注册

【bzoj1901】dynamic ranking(带修改主席树)

传送门(权限)

传送门(非权限)

花了一晚上总算把代码调好了……才知道待修改主席树怎么操作……

然而还是一知半解orz……

先说说我的理解吧

我们一般建主席树的时候都是直接在序列上建的

但是如果有修改操作怎么办?

因为主席树维护的是前缀和

而树状数组刚好支持待修改前缀和

所以我们可以将主席树和树状数组一起使用

树状数组实际指向主席树上的节点

修改和查询操作用树状数组遍历,实则修改或查询主席树上的节点

 1 //minamoto
 2 #include<bits/stdc++.h>
 3 #define N 10005
 4 using namespace std;
 5 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
 6 char buf[1<<21],*p1=buf,*p2=buf;
 7 inline int read(){
 8     #define num ch-'0'
 9     char ch;bool flag=0;int res;
10     while(!isdigit(ch=getc()))
11     (ch=='-')&&(flag=true);
12     for(res=num;isdigit(ch=getc());res=res*10+num);
13     (flag)&&(res=-res);
14     #undef num
15     return res;
16 }
17 char obuf[1<<24],*o=obuf;
18 void print(int x){
19     if(x>9) print(x/10);
20     *o++=x%10+48;
21 }
22 inline int lowbit(int x){return x&(-x);}
23 int sum[N*600],L[N*600],R[N*600];
24 int xx[N],yy[N],rt[N],a[N],b[N<<1],ca[N],cb[N],cc[N];
25 int n,q,m,cnt=0,totx,toty;
26 void update(int last,int &now,int l,int r,int x,int v){
27     sum[now=++cnt]=sum[last]+v;
28     L[now]=L[last],R[now]=R[last];
29     if(l==r) return;
30     int mid=(l+r)>>1;
31     if(x<=mid) update(L[last],L[now],l,mid,x,v);
32     else update(R[last],R[now],mid+1,r,x,v);
33 }
34 int query(int l,int r,int q){
35     if(l==r) return l;
36     int x=0,mid=(l+r)>>1;
37     for(int i=1;i<=totx;++i) x-=sum[L[xx[i]]];
38     for(int i=1;i<=toty;++i) x+=sum[L[yy[i]]];
39     if(q<=x){
40         for(int i=1;i<=totx;++i) xx[i]=L[xx[i]];
41         for(int i=1;i<=toty;++i) yy[i]=L[yy[i]];
42         return query(l,mid,q);
43     }
44     else{
45         for(int i=1;i<=totx;++i) xx[i]=R[xx[i]];
46         for(int i=1;i<=toty;++i) yy[i]=R[yy[i]];
47         return query(mid+1,r,q-x);
48     }
49 }
50 void add(int x,int y){
51     int k=lower_bound(b+1,b+1+m,a[x])-b;
52     for(int i=x;i<=n;i+=lowbit(i)) update(rt[i],rt[i],1,m,k,y);
53 }
54 int main(){
55     //freopen("testdata.in","r",stdin);
56     n=read(),q=read();
57     for(int i=1;i<=n;++i)
58     b[++m]=a[i]=read();
59     for(int i=1;i<=q;++i){
60         char ch;
61         while(!isupper(ch=getc()));
62         ca[i]=read(),cb[i]=read();
63         if(ch=='Q') cc[i]=read();else b[++m]=cb[i];
64     }
65     sort(b+1,b+1+m);
66     m=unique(b+1,b+1+m)-b-1;
67     for(int i=1;i<=n;++i) add(i,1);
68     for(int i=1;i<=q;++i){
69         if(cc[i]){
70             totx=toty=0;
71             for(int j=ca[i]-1;j;j-=lowbit(j)) xx[++totx]=rt[j];
72             for(int j=cb[i];j;j-=lowbit(j)) yy[++toty]=rt[j];
73             print(b[query(1,m,cc[i])]),*o++='\n';
74         }
75         else{add(ca[i],-1),a[ca[i]]=cb[i],add(ca[i],1);}
76     }
77     fwrite(obuf,o-obuf,1,stdout);
78     return 0;
79 }

然而我太菜了不会树套树和整体二分……

这里是zcysky大佬的树套树

这里是will大爷的整体二分


相关文章

  • 我是一名项目经理,在过去的四个月里,我把一个项目带崩了(上线后频出问题,用户无法使用).在最近的几天,我每天都在反思自己,我都在问自己以下几个问题: 1.我做错了什么? 2.我在其中占有多重的因素? 以下内容,我将回答以上问题,并在最后说一 ...
  • asp.net core系列 60 Ocelot 构建服务认证示例
    一.概述 在Ocelot中,为了保护下游api资源,用户访问时需要进行认证鉴权,这需要在Ocelot 网关中添加认证服务.添加认证后,ReRoutes路由会进行身份验证,并使用Ocelot的基于声明的功能.在Startup.cs中注册认证服 ...
  • 系统掉盘,机械硬盘掉盘,固态掉盘
    之前的立式服务器当了主机打起了游戏,但是经过半年的游戏的时间发现,机子开始变得卡了?我不由得怀疑是不是机子出现老化的问题了.打开盖子一看进了灰尘,就开始清灰了,但是情况在心理暗示的情况下没有好转.这时我打游戏才了打了三个月. 不由得开始思考 ...
  • 学了很多乱七杂八的东西,但是依然停留在前端,在工作中一直和后端交流,但是不太了解数据库是怎么回事,为了加强学习,准备学习一些关于数据库相关的东西. 说起数据库可能会有很多很多,SQLServer.Oracle.Sybase等等等,还有就是要 ...
  • 目录 引入 简单工厂 抽象工厂 Spring的bean工厂 模拟Spring工厂实现 模拟IOC 引入 假设有一个司机, 需要到某个城市, 于是我们给他一辆汽车 public class Demo { public static void ...
  • 依赖注入容器-- Autofac
    目录: 一.简介 二.如何使用 2.1.基本使用 2.2.接口使用 2.3. 其他注入 2.4. 注入的生命周期   一.简介 在上一篇文章中讲到替换默认服务容器,我们选择了Autofac Autofac---Autofac是一款IOC框架 ...

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