当前位置:网站首页>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
边栏推荐
- Grid
- The 19th Zhejiang Provincial Collegiate Programming Contest 2022浙江省赛 F.EasyFix 主席树
- 解决:信息中插入avi格式的视频时,提示“unsupported video format”
- Cloud native data warehouse analyticdb MySQL user manual
- RE1 attack and defense world reverse
- JS get the key and value of the object
- Network security - install CentOS
- v-for遍历对象
- CAIP2021 初赛VP
- Two kinds of curves in embedded audio development
猜你喜欢
js 获取对象的key和value
Wechat forum exchange applet system graduation design (2) applet function
Matlab 信号处理【问答随笔·2】
Introduction to redis and jedis and redis things
漏洞复现----49、Apache Airflow 身份验证绕过 (CVE-2020-17526)
Oracle-数据库的备份与恢复
PMP项目管理考试过关口诀-1
Explain
Inftnews | the wide application of NFT technology and its existing problems
十四、数据库的导出和导入的两种方法
随机推荐
re1攻防世界逆向
云原生正在吞噬一切,开发者该如何应对?
Installing vmtools is gray
ArcGIS: two methods of attribute fusion of the same field of vector elements
The 19th Zhejiang Provincial College Programming Contest VP record + supplementary questions
Gee (III): calculate the correlation coefficient between two bands and the corresponding p value
【微服务|SCG】gateway整合sentinel
HDU 4747 Mex「建议收藏」
Redhat下安装fedora
PMP project management exam pass Formula-1
高级程序员必知必会,一文详解MySQL主从同步原理,推荐收藏
Install Fedora under RedHat
网络安全-安装CentOS
Coreseek: the second step is index building and testing
Gee (IV): calculate the correlation between two variables (images) and draw a scatter diagram
LeeCode -- 6. Zigzag transformation
Wechat forum exchange applet system graduation design completion (1) development outline
【编译原理】词法分析设计实现
The 19th Zhejiang Provincial Collegiate Programming Contest VP记录+补题
kubernetes的简单化数据存储StorageClass(建立和删除以及初步使用)