当前位置:网站首页>Bzoj 3747 poi2015 kinoman segment tree
Bzoj 3747 poi2015 kinoman segment tree
2022-07-05 19:58:00 【Full stack programmer webmaster】
Hello everyone , I meet you again , I'm the king of the whole stack , I've prepared for you today Idea Registration code .
Title Effect : Yes m spot , Each point has a weight . Now we have this m Is the length of the point n This sequence , Seek the interval , It only appears once in the correct point interval and the maximum
I thought for a long time. , Even God's title , Ben said it was a water problem …… I'm drunk
Enumerate left points For each request, right click Tree maintenance maximum
Consider the contribution of each number to the answer Record an array next Indicates the position of the next occurrence of the point on this position Then the scope of contribution of this point is [i,next[i]-1] Suppose there is no next Namely [i,n]
So we first add the contribution of all the first numbers to the answer to the line segment tree Then scan it from left to right After counting the answers every time i The contribution to the answer is removed And then put next[i] The contribution to the answer increases the segment tree
I'm also drunk with this constant …… Second to last in speed The positive solution must not be like this ……
Besides POI2015 I'm wearing the wrong age ?
#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;
}
Publisher : Full stack programmer stack length , Reprint please indicate the source :https://javaforall.cn/117735.html Link to the original text :https://javaforall.cn
边栏推荐
- Autumn byte interviewer asked you any questions? In fact, you have stepped on thunder
- Based on vs2017 and cmake GUI configuration, zxing and opencv are used in win10 x64 environment, and simple detection of data matrix code is realized
- S7-200smart uses V90 Modbus communication control library to control the specific methods and steps of V90 servo
- 安卓面试宝典,2022Android面试笔试总结
- leetcode刷题:二叉树12(二叉树的所有路径)
- Common operators and operator priority
- [OBS] qstring's UTF-8 Chinese conversion to blog printing UTF-8 char*
- 【c语言】快速排序的三种实现以及优化细节
- [FAQ] summary of common causes and solutions of Huawei account service error 907135701
- Do you know several assertion methods commonly used by JMeter?
猜你喜欢
webuploader文件上传 拖拽上传 进度监听 类型控制 上传结果监听控件
使用easyexcel模板导出的两个坑(Map空数据列错乱和不支持嵌套对象)
Xaas trap: all things serve (possible) is not what it really needs
众昂矿业:2022年全球萤石行业市场供给现状分析
安卓面试宝典,2022Android面试笔试总结
【无标题】
618 "low key" curtain call, how can baiqiushangmei join hands with the brand to cross the "uncertain era"?
Build your own website (16)
40000 word Wenshuo operator new & operator delete
Postman core function analysis - parameterization and test report
随机推荐
【obs】libobs-winrt :CreateDispatcherQueueController
处理文件和目录名
ffplay文档[通俗易懂]
[hard core dry goods] which company is better in data analysis? Choose pandas or SQL
third-party dynamic library (libcudnn.so) that Paddle depends on is not configured correctl
【c语言】快速排序的三种实现以及优化细节
Webuploader file upload drag upload progress monitoring type control upload result monitoring control
[Collection - industry solutions] how to build a high-performance data acceleration and data editing platform
Securerandom things | true and false random numbers
C language OJ gets PE, OJ of ACM introduction~
Go language learning tutorial (XV)
Summer Challenge harmonyos - realize message notification function
acm入门day1
Tasks in GStreamer
ICTCLAS用的字Lucene4.9捆绑
How about testing outsourcing companies?
Win10 x64环境下基于VS2017和cmake-gui配置使用zxing以及opencv,并实现data metrix码的简单检测
Wildcard selector
Is it safe for Guosen Securities to open an account online?
【obs】QString的UTF-8中文转换到blog打印 UTF-8 char*