BZOJ4695：最假女选手
2024-08-30 10:33:11
浅谈区间最值操作和历史最值问题：https://www.cnblogs.com/AKMer/p/10225100.html
题目传送门：https://lydsy.com/JudgeOnline/problem.php?id=4695
吉司机线段树板子大集合。所有信息都封装在一个结构体里会比开多个数组快14秒。
注意暴力\(dfs\)子树时要\(pushdown\)。
时间复杂度：\(O(nlog^2n)\)
空间复杂度：\(O(n)\)
代码如下：
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=5e5+5,inf=1e9;
int n,m;
int a[maxn];
inline int read() {
int x=0,f=1;char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
return x*f;
}
struct segment_tree {
struct tree_node {
ll sum;
int cntA,cntZ,tag,A,B,Y,Z;//A最大值，B严格次大值，Y严格次小值，Z最小值
}tree[maxn<<2];
inline void update(int p) {
tree[p].A=max(tree[p<<1].A,tree[p<<1|1].A);
tree[p].Z=min(tree[p<<1].Z,tree[p<<1|1].Z);
tree[p].sum=tree[p<<1].sum+tree[p<<1|1].sum;
tree[p].cntA=(tree[p<<1].A==tree[p].A)*tree[p<<1].cntA;
tree[p].cntA+=(tree[p<<1|1].A==tree[p].A)*tree[p<<1|1].cntA;
tree[p].cntZ=(tree[p<<1].Z==tree[p].Z)*tree[p<<1].cntZ;
tree[p].cntZ+=(tree[p<<1|1].Z==tree[p].Z)*tree[p<<1|1].cntZ;
tree[p].B=tree[p<<1|1].A!=tree[p].A?tree[p<<1|1].A:tree[p<<1|1].B;
tree[p].B=max(tree[p].B,tree[p<<1].A!=tree[p].A?tree[p<<1].A:tree[p<<1].B);
tree[p].Y=tree[p<<1|1].Z!=tree[p].Z?tree[p<<1|1].Z:tree[p<<1|1].Y;
tree[p].Y=min(tree[p].Y,tree[p<<1].Z!=tree[p].Z?tree[p<<1].Z:tree[p<<1].Y);
}
inline void build(int p,int l,int r) {
if(l==r) {
tree[p].cntA=tree[p].cntZ=1;
tree[p].sum=tree[p].A=tree[p].Z=a[l];
tree[p].B=-inf,tree[p].Y=inf;
return;
}
int mid=(l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
update(p);
}
inline void add_tag(int p,int l,int r,int v) {
tree[p].A+=v,tree[p].Z+=v,tree[p].tag+=v;
if(tree[p].Y!=inf)tree[p].Y+=v;
if(tree[p].B!=-inf)tree[p].B+=v;
tree[p].sum+=1ll*(r-l+1)*v;
}
inline void max_tag(int p,int v) {
tree[p].sum+=1ll*tree[p].cntZ*(v-tree[p].Z),tree[p].Z=v;
if(tree[p].Y==inf)tree[p].A=v;
else tree[p].B=max(tree[p].B,v);
}
inline void min_tag(int p,int v) {
tree[p].sum-=1ll*tree[p].cntA*(tree[p].A-v),tree[p].A=v;
if(tree[p].B==-inf)tree[p].Z=v;
else tree[p].Y=min(tree[p].Y,v);
}
inline void solveMax(int p,int l,int r,int limit) {
if(limit<=tree[p].Z)return;
if(limit>tree[p].Z&&limit<tree[p].Y) {
max_tag(p,limit);
return;
}
int mid=(l+r)>>1;push_down(p,l,r);
solveMax(p<<1,l,mid,limit);
solveMax(p<<1|1,mid+1,r,limit);
update(p);
}
inline void solveMin(int p,int l,int r,int limit) {
if(limit>=tree[p].A)return;
if(limit<tree[p].A&&limit>tree[p].B) {
min_tag(p,limit);
return;
}
int mid=(l+r)>>1;push_down(p,l,r);
solveMin(p<<1,l,mid,limit);
solveMin(p<<1|1,mid+1,r,limit);
update(p);
}
inline void push_down(int p,int l,int r) {
int mid=(l+r)>>1;
if(tree[p].tag) {
add_tag(p<<1,l,mid,tree[p].tag);
add_tag(p<<1|1,mid+1,r,tree[p].tag);
tree[p].tag=0;
}
solveMin(p<<1,l,mid,tree[p].A);
solveMin(p<<1|1,mid+1,r,tree[p].A);
solveMax(p<<1,l,mid,tree[p].Z);
solveMax(p<<1|1,mid+1,r,tree[p].Z);
}
inline void ADD(int p,int l,int r,int L,int R,int v) {
if(L<=l&&r<=R) {
add_tag(p,l,r,v);
return;
}
int mid=(l+r)>>1;push_down(p,l,r);
if(L<=mid)ADD(p<<1,l,mid,L,R,v);
if(R>mid)ADD(p<<1|1,mid+1,r,L,R,v);
update(p);
}
inline void MAX(int p,int l,int r,int L,int R,int v) {
if(tree[p].Z>=v)return;
if(L<=l&&r<=R) {
solveMax(p,l,r,v);
return;
}
int mid=(l+r)>>1;push_down(p,l,r);
if(L<=mid)MAX(p<<1,l,mid,L,R,v);
if(R>mid)MAX(p<<1|1,mid+1,r,L,R,v);
update(p);
}
inline void MIN(int p,int l,int r,int L,int R,int v) {
if(tree[p].A<=v)return;
if(L<=l&&r<=R) {
solveMin(p,l,r,v);
return;
}
int mid=(l+r)>>1;push_down(p,l,r);
if(L<=mid)MIN(p<<1,l,mid,L,R,v);
if(R>mid)MIN(p<<1|1,mid+1,r,L,R,v);
update(p);
}
inline ll querySum(int p,int l,int r,int L,int R) {
if(L<=l&&r<=R)return tree[p].sum;
int mid=(l+r)>>1;ll res=0;push_down(p,l,r);
if(L<=mid)res=querySum(p<<1,l,mid,L,R);
if(R>mid)res+=querySum(p<<1|1,mid+1,r,L,R);
return res;
}
inline int queryMax(int p,int l,int r,int L,int R) {
if(L<=l&&r<=R)return tree[p].A;
int mid=(l+r)>>1,res=-inf;push_down(p,l,r);
if(L<=mid)res=max(res,queryMax(p<<1,l,mid,L,R));
if(R>mid)res=max(res,queryMax(p<<1|1,mid+1,r,L,R));
return res;
}
inline int queryMin(int p,int l,int r,int L,int R) {
if(L<=l&&r<=R)return tree[p].Z;
int mid=(l+r)>>1,res=inf;push_down(p,l,r);
if(L<=mid)res=min(res,queryMin(p<<1,l,mid,L,R));
if(R>mid)res=min(res,queryMin(p<<1|1,mid+1,r,L,R));
return res;
}
}T;
int main() {
n=read();
for(int i=1;i<=n;i++)
a[i]=read();
T.build(1,1,n);
m=read();
for(int i=1;i<=m;i++) {
int opt=read(),l=read(),r=read(),v=(opt<4?read():0);
if(opt==1)T.ADD(1,1,n,l,r,v);
if(opt==2)T.MAX(1,1,n,l,r,v);
if(opt==3)T.MIN(1,1,n,l,r,v);
if(opt==4)printf("%lld\n",T.querySum(1,1,n,l,r));
if(opt==5)printf("%d\n",T.queryMax(1,1,n,l,r));
if(opt==6)printf("%d\n",T.queryMin(1,1,n,l,r));
}
return 0;
}
最新文章
- GP 环境参数名称列表
- Android QQ群：343816731 欢迎大家加入探讨
- 如何解决EditText使用时，点击外侧系统键盘不消失的bug
- 循序渐进Python3（三） -- 1 -- 内置函数
- Kaggle Bike Sharing Demand Prediction – How I got in top 5 percentile of participants?
- Struts2+Spring集成合并
- C#神器 委托 + Unity神器 协程
- chrome 全屏 的两种方式
- Hotspot Java虚拟机的类加载器
- python中类与对象之继承
- HEU预热赛
- bzoj1801: [Ahoi2009]chess 中国象棋 dp
- Java JDBC基本用法
- django第一课 简单的网页视图
- Angular-学习。
- 解题：NOI 2009 管道取珠
- Buildroot make网卡interfaces文件被修改
- 完美解决 开机无法启动 提示0xc000000e
- webstorm添加自定义代码块
- python网络编程学习笔记（10）：webpy框架