【题解】Luogu P5324 [BJOI2019]删数
2024-09-02 03:11:00
原题传送门
易知这个数列的顺序是不用考虑的
我们看两个数列 \(1,2,3\)和\(3,3,3\)都能删完，再看两个数列\(1,2,3,4\)和\(2,2,4,4\)，也都能删完
不难发现，我们珂以把这些数字塞进桶中，记\(cnt_i\)表示数字\(i\)出现的次数，对于每个\(i\)，在一颗线段树上把区间\([i-cnt_i+1,i]\)赋值成1（因为一次删\(cnt_i\)个珂以转化成每次删\(1\)个，值从大向小递减），最后看[1,n]上有几个点不是1，这就是题目所求的答案
单点修改就直接在线段树上单点修改，区间加减实际就相当于线段树值域平移，但这个实在太麻烦，相对的，我们珂以平移查询区间
我们珂以一开始就把\(1\)设为\(Max(n,m)+1\)这样就不用考虑负数的问题了
时间复杂度是\(O(m\log (2*Max(n,m)+n))\)
假·完整代码（这个是假算法）
#include <bits/stdc++.h>
#define N 450005
#define M 150005
#define getchar nc
using namespace std;
inline char nc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
register int x=0,f=1;register char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*f;
}
inline void write(register int x)
{
if(!x)putchar('0');if(x<0)x=-x,putchar('-');
static int sta[20];register int tot=0;
while(x)sta[tot++]=x%10,x/=10;
while(tot)putchar(sta[--tot]+48);
}
int n,m,a[M],lim,cnt[N],w;
int tr[N<<3],sum[N];
inline void modify(register int x,register int l,register int r,register int pos,register int val)
{
if(l==r)
{
tr[x]=val;
return;
}
int mid=l+r>>1;
if(pos<=mid)
modify(x<<1,l,mid,pos,val);
else
modify(x<<1|1,mid+1,r,pos,val);
tr[x]=tr[x<<1]+tr[x<<1|1];
}
inline int query(register int x,register int l,register int r,register int L,register int R)
{
if(L<=l&&r<=R)
return tr[x];
int mid=l+r>>1,res=0;
if(L<=mid)
res+=query(x<<1,l,mid,L,R);
if(R>mid)
res+=query(x<<1|1,mid+1,r,L,R);
return res;
}
int main()
{
n=read(),m=read();
lim=m+n*2;
memset(cnt,0,sizeof(cnt));
memset(sum,0,sizeof(sum));
for(register int i=1;i<=n;++i)
{
a[i]=read();
if((++sum[n+a[i]-cnt[a[i]+m]])==1)
modify(1,1,lim,n+a[i]-cnt[a[i]+m],1);
++cnt[a[i]+m];
}
for(register int i=1;i<=m;++i)
{
int opt=read(),x=read();
if(opt)
{
x-=w;
--cnt[a[opt]+m];
if((--sum[n+a[opt]-cnt[a[opt]+m]])==0)
modify(1,1,lim,n+a[opt]-cnt[a[opt]+m],0);
a[opt]=x;
if((++sum[n+a[opt]-cnt[a[opt]+m]])==1)
modify(1,1,lim,n+a[opt]-cnt[a[opt]+m],1);
++cnt[a[opt]+m];
}
else
w+=x;
write(n-query(1,1,lim,n+1-w,n+n-w)),puts("");
}
return 0;
}
交一发，发现会WA46
实际因为我们有种情况没有考虑：当\(val>n\)时，所有的都要修改，然而到线段树上就变成了一段区间，会对答案造成影响
我们只需要动态插入/删除区间即可，这样线段树要维护区间最小值及其个数
真·完整代码
#include <bits/stdc++.h>
#define N 450005
#define M 150005
#define getchar nc
using namespace std;
inline char nc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
register int x=0,f=1;register char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*f;
}
inline void write(register int x)
{
if(!x)putchar('0');if(x<0)x=-x,putchar('-');
static int sta[20];register int tot=0;
while(x)sta[tot++]=x%10,x/=10;
while(tot)putchar(sta[--tot]+48);
}
inline int Max(register int a,register int b)
{
return a>b?a:b;
}
int n,m,a[M],b[N],cnt[N],c,ql,qr,lim;
int minn[N<<3],sum[N<<3],tag[N<<3];
inline void pushup(register int x)
{
int ls=x<<1,rs=x<<1|1;
minn[x]=minn[ls],sum[x]=sum[ls];
if(minn[rs]<minn[x])
minn[x]=minn[rs],sum[x]=sum[rs];
else if(minn[rs]==minn[x])
sum[x]+=sum[rs];
}
inline void build(register int x,register int l,register int r)
{
if(l==r)
{
minn[x]=b[l];
sum[x]=1;
return;
}
int mid=l+r>>1;
build(x<<1,l,mid);
build(x<<1|1,mid+1,r);
pushup(x);
}
inline void pushdown(register int x)
{
if(tag[x])
{
int ls=x<<1,rs=x<<1|1;
tag[ls]+=tag[x],tag[rs]+=tag[x];
minn[ls]+=tag[x],minn[rs]+=tag[x];
tag[x]=0;
}
}
inline void modify(register int x,register int l,register int r,register int L,register int R,register int val)
{
if(L<=l&&r<=R)
{
minn[x]+=val;
tag[x]+=val;
return;
}
int mid=l+r>>1;
pushdown(x);
if(L<=mid)
modify(x<<1,l,mid,L,R,val);
if(R>mid)
modify(x<<1|1,mid+1,r,L,R,val);
pushup(x);
}
inline int query(register int x,register int l,register int r,register int L,register int R)
{
if(L<=l&&r<=R)
return minn[x]?0:sum[x];
int mid=l+r>>1,res=0;
pushdown(x);
if(L<=mid)
res+=query(x<<1,l,mid,L,R);
if(R>mid)
res+=query(x<<1|1,mid+1,r,L,R);
return res;
}
int main()
{
n=read(),m=read();
c=Max(n,m);
for(register int i=1;i<=n;++i)
{
a[i]=read();
++cnt[a[i]+=c];
}
ql=c+1,qr=c+n,lim=c*2+n;
for(register int i=m+1;i<=qr;++i)
++b[i-cnt[i]+1],--b[i+1];
for(register int i=2;i<=qr+1;++i)
b[i]+=b[i-1];
build(1,1,lim);
for(register int i=1;i<=m;++i)
{
int opt=read(),x=read();
if(opt)
{
--cnt[a[opt]];
if(a[opt]<=qr)
modify(1,1,lim,a[opt]-cnt[a[opt]],a[opt]-cnt[a[opt]],-1);
a[opt]=x+ql-1;
modify(1,1,lim,a[opt]-cnt[a[opt]],a[opt]-cnt[a[opt]],1);
++cnt[a[opt]];
}
else
{
if(x==1)
{
if(cnt[qr])
modify(1,1,lim,qr-cnt[qr]+1,qr,-1);
--ql,--qr;
}
else
{
++ql,++qr;
if(cnt[qr])
modify(1,1,lim,qr-cnt[qr]+1,qr,1);
}
}
write(query(1,1,lim,ql,qr)),puts("");
}
return 0;
}
最新文章
- Sprint计划
- UNICODE 7.0定义的表情符
- AngularJS Best Practices: ui-router
- web工程 所需是jar包总结
- HDU 4902 Nice boat --线段树(区间更新)
- php时间函数整理
- C# Socket连接请求超时机制
- 通过 ANE(Adobe Native Extension) 启动Andriod服务 推送消息(三)
- PythonCrawl自学日志（4）
- velocity-1.7学习笔记
- Protobuf的自动反射消息类型的方法
- Windows Azure功能更新：Oracle软件正式登陆Azure了
- Go的String转码包
- 八、VueJs 填坑日记之参数传递及内容页面的开发
- canvas实现倒计时效果示例（vue组件内编写）
- nyoj44 子串和 线性DP
- 20145237 《Java程序设计》第八周学习总结
- 面试常用算法总结——排序算法（java版）
- 056 Java搭建kafka环境
- PHP 二位数组按照下标排序
热门文章
- 自制Amiibo 踩坑/填坑 指南
- dajngo控制台添加数据报错Requested setting DEFAULT_INDEX_TABLESPACE, but settings are not configured.
- 第09组 Alpha冲刺（1/6）
- [技术博客]JSCover+selenium获得js代码覆盖率
- java join()基本用法与说明解释
- python操作mysql基础一
- JVM探究之 —— 类加载过程
- 【C++】C++中重载运算符和类型转换
- centos 查看版本 及 升级
- StarGAN: Unified Generative Adversarial Networks for Multi-Domain Image-to-Image Translation - 1 - 多个域间的图像翻译论文学习