建设网站的公司要什么资质,网站实名,seo推广原理,泰安百度推广代理商传送门 文章目录题意#xff1a;思路#xff1a;题意#xff1a;
给你一个长度为nnn的数组#xff0c;对每个位置iii求一个最大价值#xff0c;价值计算方式如下#xff1a;选择一个包含iii的[l,r][l,r][l,r]#xff0c;让后将其拿出来排序#xff0c;之后价值就是当前…传送门
文章目录题意思路题意
给你一个长度为nnn的数组对每个位置iii求一个最大价值价值计算方式如下选择一个包含iii的[l,r][l,r][l,r]让后将其拿出来排序之后价值就是当前位置的值aia_iai在排序后的位置到中位数的位置的距离如果有相同的值位置可以任意安排中位数的位置定义为如果长度为奇数位置就是lr2\frac{lr}{2}2lr否则lr12\frac{lr1}{2}2lr1。
思路
对于每个位置我们可以想到分两种情况贪心一种是让≤ai\le a_i≤ai的尽可能多另一种是让≥ai\ge a_i≥ai的尽可能多我们只讨论第一种就是让≤ai\le a_i≤ai的尽可能多。 在确定aia_iai之后就有一个比较套路的做法了我们可以将aia_iai的都设为−1-1−1≤ai\le a_i≤ai的都设为111这样我们就可以从[i1,n][i1,n][i1,n]找一个值最大的前缀从[1,i−1][1,i-1][1,i−1]找一个值最大的后缀让后二者结合起来为sumsumsum答案就是sum2\frac{sum}{2}2sum。现在问题就转换成如何快速求最长前缀和最长后缀了。 这也是一个经典问题将其放在线段树上维护个lmax,rmax,sumlmax,rmax,sumlmax,rmax,sum即可。 目前我们这个问题已经解决了一半了现在是如何将≤ai\le a_i≤ai的都赋为111aia_iai的赋为−1-1−1呢我们不能每次都暴力修改考虑将每个值对应的ididid都放在一个桶里初始的时候让每个位置都为−1-1−1让后从[1,n][1,n][1,n]遍历这个桶每次将当前桶内的ididid位置都变成111即可这样放在桶里就可以很好的解决这个问题了。 对于另一种情况他的答案应该为sum12\frac{sum1}{2}2sum1这个跟中位数的位置有关系偶数的话中位数是靠近右边的内个数所以如果sumsumsum表示的是≥ai\ge a_i≥ai的个数的话那么aia_iai在最左边所以要上取整。
// Problem: F. Strange Array
// Contest: Codeforces - Codeforces Round #727 (Div. 2)
// URL: https://codeforces.com/contest/1539/problem/F
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize(Ofast,no-stack-protector,unroll-loops,fast-math)
//#pragma GCC target(sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tunenative)
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#includerandom
#includecassert
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].ltr[u].r)1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N200010,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int n,m;
int ans[N];
struct node {int val,id;bool operator (const node W) const {return valW.val;}
}a[N];
vectornodev[N];
struct Node
{int l,r;int sum,smax,lmax,rmax;
}tr[N*4];void pushup(Node a,Node l,Node r)
{a.suml.sumr.sum;a.lmaxmax(l.lmax,l.sumr.lmax);a.rmaxmax(r.rmax,r.suml.rmax);//a.smaxmax(max(l.smax,r.smax),l.rmaxr.lmax);
}void pushup(int u)
{pushup(tr[u],tr[u1],tr[u1|1]);
}void build(int u,int l,int r,int c)
{if(lr) {tr[u]{l,r,c,c,c,c};return;}tr[u].ll,tr[u].rr;int mid(tr[u].ltr[u].r)1;build(u1,l,mid,c),build(u1|1,mid1,r,c);pushup(u);
}void modify(int u,int x,int c)
{if(tr[u].lxtr[u].rx) tr[u]{x,x,c,c,c,c};else{int mid(tr[u].ltr[u].r)1;if(xmid) modify(u1,x,c);else modify(u1|1,x,c);pushup(u);}
}Node query(int u,int l,int r)
{if(lr) return {0,0,0,0,0,0};if(tr[u].lltr[u].rr) return tr[u];int mid(tr[u].ltr[u].r)1;if(rmid) return query(u1,l,r);else if(lmid) return query(u1|1,l,r);else {Node a,b,ans;aquery(u1,l,r);bquery(u1|1,l,r);pushup(ans,a,b);return ans;}
}int main()
{cinn;for(int i1;in;i) {scanf(%d,a[i].val);a[i].idi;v[a[i].val].pb(a[i]);}build(1,1,n,-1);for(int i1;in;i) {for(auto x:v[i]) modify(1,x.id,1);for(auto x:v[i]) {Node rquery(1,x.id1,n),lquery(1,1,x.id-1);ans[x.id]max(ans[x.id],(l.rmax)/2);ans[x.id]max(ans[x.id],(r.lmax)/2);ans[x.id]max(ans[x.id],(l.rmaxr.lmax)/2);//if(x.id7) coutl.lmax r.lmaxendl;}//if(i2) coutans[4]endl;//if(i4) coutans[2]endl; }build(1,1,n,-1);for(int in;i1;i--) {for(auto x:v[i]) modify(1,x.id,1);for(auto x:v[i]) {Node rquery(1,x.id1,n),lquery(1,1,x.id-1);ans[x.id]max(ans[x.id],(l.rmax1)/2);ans[x.id]max(ans[x.id],(r.lmax1)/2);ans[x.id]max(ans[x.id],(l.rmaxr.lmax1)/2);//if(x.id1) couti r.lmax l.rmaxendl;//if(i2) coutr.lmaxendl;}//if(i2) coutans[4]endl;}for(int i1;in;i) printf(%d ,ans[i]); puts();return 0;
}
