当前位置:网站首页>HDU 4747 Mex「建议收藏」
HDU 4747 Mex「建议收藏」
2022-07-07 21:51:00 【全栈程序员站长】
大家好,又见面了,我是全栈君。
题意:
给出一段数字a 定义mex(l,r)表示a[l]…a[r]中最小的不连续的数字 求出全部mex(l,r)的和
思路:
首先能够想到由l開始到n的全部数字的mex值必定是递增的 那么就能够求出以1開始到n的全部数字的mex 从前到后扫一遍就可以 这时能够求出[1,r]全部区间的mex和 利用线段树就可以
接着考虑怎样求[2,r]、[3,r]…. 由[1,r]到[2,r]的转变无非是去掉第一个数字 那么去掉一个数字的影响是什么呢?
比方去掉一个2 那他最多影响到下一个2出现的地方 并且 他仅仅是把mex>2的地方改成了2 即从2处截断 又由于之前所说的递增关系 所以影响的区间也一定是连续的!
那么我们就能够每次删掉一个数字 利用线段树找出他影响的区间 并把这个区间覆盖为那个删掉的数字
最后每次求和就是答案
代码:
#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;
}
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/116215.html原文链接:https://javaforall.cn
边栏推荐
猜你喜欢
Binary tree
Inftnews | the wide application of NFT technology and its existing problems
微信论坛交流小程序系统毕业设计毕设(2)小程序功能
七月第一周
GEE(四):计算两个变量(影像)之间的相关性并绘制散点图
leetcode-520. 检测大写字母-js
V20变频器手自动切换(就地远程切换)的具体方法示例
二叉树(Binary Tree)
Install a new version of idea. Double click it to open it
JMeter interface automated test read case, execute and write back result
随机推荐
opencv scalar传入三个参数只能显示黑白灰问题解决
Dynamic agent explanation (July 16, 2020)
U盘拷贝东西时,报错卷错误,请运行chkdsk
Specific method example of V20 frequency converter manual automatic switching (local remote switching)
Archlinux install MySQL
网络安全-安装CentOS
Coreseek: the second step is index building and testing
Redhat下安装fedora
海内外技术人们“看”音视频技术的未来
leetcode-520. 检测大写字母-js
系统架构设计师备考经验分享:论文出题方向
[microservices SCG] gateway integration Sentinel
十四、数据库的导出和导入的两种方法
微信论坛交流小程序系统毕业设计毕设(8)毕业设计论文模板
Installing vmtools is gray
Tree background data storage (using webmethod) [easy to understand]
Wechat forum exchange applet system graduation design completion (7) Interim inspection report
云原生数据仓库AnalyticDB MySQL版用户手册
Network security sqlmap and DVWA explosion
十三、系统优化