2018.08.01 BZOJ4552: [Tjoi2016&Heoi2016]排序(二分+线段树)
2024-10-11 12:14:16
传送门
线段树简单题。
二分答案+线段树排序。
实际上就是二分答案mid" role="presentation" style="position: relative;">midmid,然后把比mid" role="presentation" style="position: relative;">midmid小的全部变成0" role="presentation" style="position: relative;">00,不比mid" role="presentation" style="position: relative;">midmid小的全部变成1" role="presentation" style="position: relative;">11,然后用线段树维护01" role="presentation" style="position: relative;">0101排序。
时间效率O(mlogn)" role="presentation" style="position: relative;">O(mlogn)O(mlogn)。
代码:
#include<bits/stdc++.h>
#define lc (p<<1)
#define rc (p<<1|1)
#define mid (T[p].l+T[p].r>>1)
#define N 100005
using namespace std;
int n,m,a[N],b[N],l,r,pos;
struct Node{int l,r,cov,sum;}T[N<<2];
struct Query{int op,l,r;}q[N];
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
inline void pushup(int p){T[p].sum=T[lc].sum+T[rc].sum;}
inline void pushnow(int p,int v){T[p].cov=v,T[p].sum=(T[p].r-T[p].l+1)*v;}
inline void pushdown(int p){if(T[p].cov!=-1)pushnow(lc,T[p].cov),pushnow(rc,T[p].cov),T[p].cov=-1;}
inline void build(int p,int l,int r){
T[p].l=l,T[p].r=r,T[p].cov=-1;
if(l==r){T[p].sum=b[l];return;}
build(lc,l,mid),build(rc,mid+1,r),pushup(p);
}
inline void update(int p,int ql,int qr,int v){
if(ql>T[p].r||qr<T[p].l)return;
if(ql<=T[p].l&&T[p].r<=qr)return pushnow(p,v);
pushdown(p);
if(qr<=mid)update(lc,ql,qr,v);
else if(ql>mid)update(rc,ql,qr,v);
else update(lc,ql,mid,v),update(rc,mid+1,qr,v);
pushup(p);
}
inline int query(int p,int ql,int qr){
if(ql>T[p].r||qr<T[p].l)return 0;
if(ql<=T[p].l&&T[p].r<=qr)return T[p].sum;
pushdown(p);
if(qr<=mid)return query(lc,ql,qr);
if(ql>mid)return query(rc,ql,qr);
return query(lc,ql,mid)+query(rc,mid+1,qr);
}
inline bool check(int x){
for(int i=1;i<=n;++i)b[i]=(a[i]>=x);
build(1,1,n);
for(int i=1;i<=m;++i){
int num=query(1,q[i].l,q[i].r);
if(!q[i].op)update(1,q[i].r-num+1,q[i].r,1),update(1,q[i].l,q[i].r-num,0);
else update(1,q[i].l,q[i].l+num-1,1),update(1,q[i].l+num,q[i].r,0);
}
return query(1,pos,pos);
}
int main(){
n=read(),m=read(),l=1,r=n;
for(int i=1;i<=n;++i)a[i]=read();
for(int i=1;i<=m;++i)q[i].op=read(),q[i].l=read(),q[i].r=read();
pos=read();
while(l<=r){
int midd=l+r>>1;
if(check(midd))l=midd+1;
else r=midd-1;
}
if(check(r))printf("%d",r);
else printf("%d",l);
return 0;
}
最新文章
- Python for Infomatics 第13章 网页服务一(译)
- error C4996: &#39;fopen&#39;: This function or variable may be unsafe.
- 解决安装VS2013提示“已停止工作”问题
- ChinaUnix上的帮助手册还不错!
- XmlHttp对象
- C题
- fastclick原理剖析及其用法
- CSS3_元素拖曳原理_设置全局点击捕获_九宫格碰撞检测_自定义滚动条
- 011 pandas的常见操作
- Python实现的各种机器学习算法
- require 与 include 的区别
- Windows下卸载Apache、Mysql
- QT中的线程与事件循环理解(2)
- vi 编辑器使用技巧
- Codeforces Round #296 (Div. 2) B. Error Correct System
- java 读取excel 2007 .xlsx文件 poi实现
- Android 全面插件化 RePlugin 流程与源码解析
- linux下后台运行jar包
- PDF快速创建目录
- C# 接口中的索引器
热门文章
- RabbitMQ-从基础到实战(4)— 消息的交换(中)
- Spring声明式事务不回滚问题
- 基于OpenGL编写一个简易的2D渲染框架-02 搭建OpenGL环境
- <;!-- str.startsWith(&#39;胡&#39;) 检查一个 字符串中是否有某字符 返回true false -->;&; vh 属性
- Python itertools/内置函数
- org.Hs.eg.db包简介(转换NCBI、ensemble等数据库中基因ID,symbol等之间的转换)
- MongoDB 分片副本集集群搭建
- JPA报错, java.lang.NullPointerException
- 4. Median of Two Sorted Arrays(Array; Divide-and-Conquer)
- 兼容主流浏览器的css渐变色