当前位置:网站首页>HDU 4747 mex "recommended collection"
HDU 4747 mex "recommended collection"
2022-07-07 23:23:00 【Full stack programmer webmaster】
Hello everyone , I meet you again , I'm the king of the whole stack .
The question :
Give a number a Definition mex(l,r) Express a[l]…a[r] The smallest discontinuous number in Find all mex(l,r) And
Ideas :
First of all, I can think of l Start to n Of all numbers mex The value must be increasing Then we can find out with 1 Start to n Of all numbers mex Sweep it from front to back At this time, we can find [1,r] All interval mex and Using the segment tree
Then consider how to find [2,r]、[3,r]…. from [1,r] To [2,r] The change of is nothing more than removing the first number So what is the effect of removing a number ?
For example, remove one 2 Then he can affect the next one at most 2 Where it appears also He just put mex>2 The place was changed to 2 From 2 There's a cut And because of the increasing relationship mentioned before So the range of influence must also be continuous !
Then we can delete one number at a time Use the line segment tree to find out the interval of his influence And cover this interval with the deleted number
Finally, every summation is the answer
Code :
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
typedef __int64 ll;
#define N 201000
#define L(x) (x<<1)
#define R(x) ((x<<1)|1)
struct node
{
int l,r,val,lazy;
ll sum;
}tree[N*4];
int a[N],mex[N],next[N];
int n,l,r;
map<int,int> mp;
ll ans;
void up(int i)
{
tree[i].val=max(tree[L(i)].val,tree[R(i)].val);
tree[i].sum=tree[L(i)].sum+tree[R(i)].sum;
}
void down(int i)
{
if(tree[i].lazy!=-1)
{
tree[L(i)].lazy=tree[i].lazy;
tree[L(i)].val=tree[i].lazy;
tree[L(i)].sum=(tree[L(i)].r-tree[L(i)].l+1)*tree[i].lazy;
tree[R(i)].lazy=tree[i].lazy;
tree[R(i)].val=tree[i].lazy;
tree[R(i)].sum=(tree[R(i)].r-tree[R(i)].l+1)*tree[i].lazy;
tree[i].lazy=-1;
}
}
void init(int l,int r,int i)
{
tree[i].l=l; tree[i].r=r; tree[i].lazy=-1;
if(l==r)
{
tree[i].val=mex[l];
tree[i].sum=mex[l];
return ;
}
int mid=(l+r)>>1;
init(l,mid,L(i));
init(mid+1,r,R(i));
up(i);
}
void update(int l,int r,int i,int k)
{
if(l==tree[i].l&&r==tree[i].r)
{
tree[i].sum=(tree[i].r-tree[i].l+1)*k;
tree[i].val=k;
tree[i].lazy=k;
return ;
}
down(i);
int mid=(tree[i].l+tree[i].r)>>1;
if(r<=mid) update(l,r,L(i),k);
else if(l>mid) update(l,r,R(i),k);
else
{
update(l,mid,L(i),k);
update(mid+1,r,R(i),k);
}
up(i);
}
void query(int i,int k)
{
if(tree[i].l==tree[i].r)
{
if(tree[i].val>k) l=tree[i].l;
else l=n+1;
return ;
}
down(i);
if(tree[L(i)].val>k) query(L(i),k);
else query(R(i),k);
up(i);
}
int main()
{
int i,j;
while(~scanf("%d",&n))
{
if(!n) break;
mp.clear(); // get mex
j=0;
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
mp[a[i]]=1;
while(mp[j]) j++;
mex[i]=j;
}
mp.clear(); // get next
for(i=1;i<=n;i++) mp[a[i]]=n+1;
for(i=n;i>=1;i--)
{
next[i]=mp[a[i]];
mp[a[i]]=i;
}
//for(i=1;i<=n;i++) printf("%d %d\n",mex[i],next[i]);
init(1,n,1);
for(i=1,ans=0;i<=n;i++)
{
ans+=tree[1].sum;
query(1,a[i]);
r=next[i];
//printf("%d %d\n",l,r);
if(l<r)
{
update(l,r-1,1,a[i]);
}
update(i,i,1,0);
}
printf("%I64d\n",ans);
}
return 0;
}
Publisher : Full stack programmer stack length , Reprint please indicate the source :https://javaforall.cn/116215.html Link to the original text :https://javaforall.cn
边栏推荐
- Ros2 topic (03): the difference between ros1 and ros2 [02]
- 位运算(Bit Operation)
- PCI-Express接口的PCB布线规则
- The 19th Zhejiang Provincial College Programming Contest VP record + supplementary questions
- Count the top 10 films at the box office and save them in another file
- Installing spss25
- Binary tree
- Technology at home and abroad people "see" the future of audio and video technology
- 智慧社区和智慧城市之间有什么异同
- Why does the market need low code?
猜你喜欢
Matlab 信号处理【问答随笔·2】
海内外技术人们“看”音视频技术的未来
成年人只有一份主业是要付出代价的,被人事劝退后,我哭了一整晚
Wechat forum exchange applet system graduation design (5) assignment
经纬度PLT文件格式说明
Wechat forum exchange applet system graduation design completion (7) Interim inspection report
Oracle-数据库的备份与恢复
JMeter-接口自动化测试读取用例,执行并结果回写
聊聊支付流程的设计与实现逻辑
LeeCode -- 6. Z 字形变换
随机推荐
Kubernetes' simplified data storage storageclass (creation, deletion and initial use)
Mysql索引优化实战一
ROS2专题(03):ROS1和ROS2的区别【01】
In the field of software engineering, we have been doing scientific research for ten years!
微信论坛交流小程序系统毕业设计毕设(1)开发概要
Unity3D学习笔记5——创建子Mesh
智慧社区和智慧城市之间有什么异同
Bea-3xxxxx error code
网络安全-beef
Grid
Quelles sont les similitudes et les différences entre les communautés intelligentes et les villes intelligentes?
Matlab SEIR infectious disease model prediction
PMP project management exam pass Formula-1
FreeLink开源呼叫中心设计思想
Dynamics 365 find field filtering
LDO穩壓芯片-內部框圖及選型參數
Install Fedora under RedHat
Cloud native is devouring everything. How should developers deal with it?
LDO voltage stabilizing chip - internal block diagram and selection parameters
Unity3d learning notes 4 - create mesh advanced interface