大家好,又见面了,我是全栈君,今天给大家准备了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; }
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117735.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...