当前位置:网站首页>BZOJ 3747 POI2015 Kinoman 段树
BZOJ 3747 POI2015 Kinoman 段树
2022-07-05 19:53:00 【全栈程序员站长】
大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。
标题效果:有m点,每个点都有一个权值。现在我们有这个m为点的长度n该序列,寻求区间,它仅出现一次在正确的点区间内值和最大
想了很久,甚至神标题,奔说是水的问题……我醉了
枚举左点 对于每个请求留点右键点 树维护最大值
考虑每一个数对答案的贡献 记录一个数组next表示这个位置上的点下一次出现的位置 那么这个点贡献的作用范围就是[i,next[i]-1] 假设没有next就是[i,n]
于是我们先把全部第一个出现的数对答案的贡献增加线段树 然后从左到右扫一遍 每次统计完答案之后把i对答案的贡献去除 然后把next[i]对答案的贡献增加线段树
这常数我也是醉了……速度倒数第二啥的 正解一定不是这种……
此外POI2015是我穿错年代了?
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 1001001
using namespace std;
struct Segtree{
Segtree *ls,*rs;
long long num,mark;
void Build_Tree(int x,int y);
void Update(int x,int y,int l,int r,long long val);
long long Get_Ans(int x,int y,int l,int r);
}*root=new Segtree,mempool[M<<1],*C=mempool;
int n,m;
int a[M],w[M],next[M],last[M];
bool v[M];
long long ans;
void Segtree :: Build_Tree(int x,int y)
{
int mid=x+y>>1;
num=0;mark=0;
if(x==y) return ;
ls=C++;rs=C++;
ls->Build_Tree(x,mid);
rs->Build_Tree(mid+1,y);
}
void Segtree :: Update(int x,int y,int l,int r,long long val)
{
int mid=x+y>>1;
if(x==l&&y==r)
{
num+=val;
mark+=val;
return ;
}
if(mark)
{
ls->num+=mark;
rs->num+=mark;
ls->mark+=mark;
rs->mark+=mark;
mark=0;
}
if(r<=mid) ls->Update(x,mid,l,r,val);
else if(l>mid) rs->Update(mid+1,y,l,r,val);
else ls->Update(x,mid,l,mid,val),rs->Update(mid+1,y,mid+1,r,val);
num=max(ls->num,rs->num);
}
long long Segtree :: Get_Ans(int x,int y,int l,int r)
{
int mid=x+y>>1;
if(x==l&&y==r)
return num;
if(mark)
{
ls->num+=mark;
rs->num+=mark;
ls->mark+=mark;
rs->mark+=mark;
mark=0;
}
if(r<=mid) return ls->Get_Ans(x,mid,l,r);
if(l> mid) return rs->Get_Ans(mid+1,y,l,r);
return max( ls->Get_Ans(x,mid,l,mid) , rs->Get_Ans(mid+1,y,mid+1,r) );
}
int main()
{
int i;
cin>>n>>m;
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
for(i=1;i<=m;i++)
scanf("%d",&w[i]);
for(i=1;i<=n;i++)
{
if(last[a[i]])
next[last[a[i]]]=i;
else
v[i]=1;
last[a[i]]=i;
}
root->Build_Tree(1,n);
for(i=1;i<=n;i++)
if(v[i])
root->Update(1,n,i,next[i]?next[i]-1:n,w[a[i]]);
for(i=1;i<=n;i++)
{
ans=max(ans, root->Get_Ans(1,n,i,n) );
root->Update(1,n,i,next[i]?next[i]-1:n,-w[a[i]]);
if(next[i])
root->Update(1,n,next[i],next[next[i]]?next[next[i]]-1:n,w[a[next[i]]]);
}
cout<<ans<<endl;
}
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/117735.html原文链接:https://javaforall.cn
边栏推荐
- 线程池参数及合理设置
- Complete interview questions for interviewers and senior Android engineers in front-line Internet enterprises
- Autumn byte interviewer asked you any questions? In fact, you have stepped on thunder
- C application interface development foundation - form control (6) - menu bar, toolbar and status bar controls
- 不愧是大佬,字节大牛耗时八个月又一力作
- 【合集- 行业解决方案】如何搭建高性能的数据加速与数据编排平台
- 使用 RepositoryProvider简化父子组件的传值
- UWB ultra wideband positioning technology, real-time centimeter level high-precision positioning application, ultra wideband transmission technology
- Analysis of openh264 decoded data flow
- What is the function of okcc call center
猜你喜欢
Do you know several assertion methods commonly used by JMeter?
如何安全快速地从 Centos迁移到openEuler
Let's talk about threadlocalinsecurerandom
S7-200smart uses V90 Modbus communication control library to control the specific methods and steps of V90 servo
淺淺的談一下ThreadLocalInsecureRandom
软件测试工程师是做什么的?待遇前景怎么样?
Worthy of being a boss, byte Daniel spent eight months on another masterpiece
Base du réseau neuronal de convolution d'apprentissage profond (CNN)
全网最全的低代码/无代码平台盘点:简道云、伙伴云、明道云、轻流、速融云、集简云、Treelab、钉钉·宜搭、腾讯云·微搭、智能云·爱速搭、百数云
[FAQ] summary of common causes and solutions of Huawei account service error 907135701
随机推荐
【硬核干货】数据分析哪家强?选Pandas还是选SQL
SecureRandom那些事|真伪随机数
third-party dynamic library (libcudnn.so) that Paddle depends on is not configured correctl
Parler de threadlocal insecurerandom
Redis cluster simulated message queue
太牛了,看这篇足矣了
Multi branch structure
Fundamentals of shell programming (Chapter 9: loop)
After 95, Alibaba P7 published the payroll: it's really fragrant to make up this
Base du réseau neuronal de convolution d'apprentissage profond (CNN)
[OBS] qstring's UTF-8 Chinese conversion to blog printing UTF-8 char*
Common operators and operator priority
股票开户哪里好?网上客户经理开户安全吗
Inventory of the most complete low code / no code platforms in the whole network: Jiandao cloud, partner cloud, Mingdao cloud, Qingliu, xurong cloud, Jijian cloud, treelab, nailing · Yida, Tencent clo
随机数生成的四种方法|Random|Math|ThreadLocalRandom|SecurityRandom
leetcode刷题:二叉树16(路径总和)
Debezium series: record the messages parsed by debezium and the solutions after the MariaDB database deletes multiple temporary tables
Database logic processing function
Relationship between floating elements and parent and brother boxes
大厂面试必备技能,2022Android不死我不倒