这玩意为啥是紫。
考虑对每个小于\(x\)的数值设为1,大于\(x\)的数值设为-1.
那么对于答案要求的就是绝对值最大的连续段。
线段树是很显然的。
考虑我们不能对每个数都进行一遍重构,这样就退化到了\(O(n^2log)\)
我们对每个数的权值排序,那么更改操作变成了\(O(nlog)\)
然后我们用线段树维护前缀和就好了。
CF1539F Strange Array
#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
#define N 200005
ll n;
ll num[N];
struct P{int v,to;}e[N];
bool operator < (P a,P b){
return a.v < b.v;
}
struct Q{ll mx,mn,tag,s;Q(){mx = 0;mn = 0;tag = 0;}}t[N << 1];//维护前缀和,支持区间加,区间min,区间max
#define l(x) (x << 1)
#define r(x) (x << 1 | 1)
#define mid ((l + r) >> 1)
inline void pushdown(int u){
t[l(u)].mn += t[u].tag;
t[r(u)].mn += t[u].tag;
t[l(u)].mx += t[u].tag;
t[r(u)].mx += t[u].tag;
t[l(u)].tag += t[u].tag;
t[r(u)].tag += t[u].tag;
t[u].tag = 0;
}
inline void up(int u){
t[u].mx = std::max(t[l(u)].mx,t[r(u)].mx);
t[u].mn = std::min(t[l(u)].mn,t[r(u)].mn);
}
ll l = 1;
inline void change(int u,int l,int r,int tl,int tr,int p){
pushdown(u);
if(tl <= l && r <= tr){
t[u].mx += p;
t[u].mn += p;
t[u].tag += p;
// std::cout<<u<<"mx:"<<t[u].mx<<"mi:"<<t[u].mn<<" "<<l<<" "<<r<<" "<<tl<<" "<<tr<<" "<<p<<std::endl;
return;
}
if(tl <= mid)
change(l(u),l,mid,tl,tr,p);
if(tr > mid)
change(r(u),mid + 1,r,tl,tr,p);
up(u);
// std::cout<<u<<"mx:"<<t[u].mx<<"mi:"<<t[u].mn<<" "<<l<<" "<<r<<" "<<tl<<" "<<tr<<" "<<p<<std::endl;
}
inline ll qx(int u,int l,int r,int tl,int tr){
if(tr == 0)
return 0;
pushdown(u);
ll ans = -0x3f3f3f3f;
if(tl <= l && r <= tr)
return t[u].mx;
if(tl <= mid)
ans = std::max(ans,qx(l(u),l,mid,tl,tr));
if(tr > mid)
ans = std::max(ans,qx(r(u),mid + 1,r,tl,tr));
return ans;
}
inline ll qi(int u,int l,int r,int tl,int tr){
// std::cout<<u<<" "<<t[u].mn<<" "<<l<<" "<<r<<" "<<tl<<" "<<tr<<std::endl;
if(tr == 0)
return 0;
pushdown(u);
ll ans = 0x3f3f3f3f;
if(tl <= l && r <= tr)
return t[u].mn;
if(tl <= mid)
ans = std::min(ans,qi(l(u),l,mid,tl,tr));
if(tr > mid)
ans = std::min(ans,qi(r(u),mid + 1,r,tl,tr));
return ans;
}
ll f[N],fa[N];
int main(){
scanf("%lld",&n);
for(int i = 1;i <= n;++i)
scanf("%lld",&num[i]);
for(int i = 1;i <= n;++i)
e[i].v = num[i],e[i].to = i;
for(int i = 1;i <= n;++i)
change(1,1,n,i,n,1);
std::sort(e + 1,e + n + 1);
for(int i = 1;i <= n;++i){
ll now = e[i].to;
std::cout<<e[i].v<<" "<<e[i].to<<":"<<std::endl;
change(1,1,n,e[i].to,n,-1);
while(e[l].v <= e[i].v && l < i){
// std::cout<<l<<" "<<std::endl;
change(1,1,n,e[l].to,n,-2);
l ++ ;
}
l = i + 1;
while(e[l].v == e[i].v){
change(1,1,n,e[l].to,n,-2)
++l;
std::cout<<l<<std::endl;
}
l -- ;
// std::cout<<qx(1,1,n,now,n)<<" "<<std::min(qi(1,1,n,1,now - 1),(ll)0)<<std::endl;
// std::cout<<qi(1,1,n,now,n)<<" "<<std::max(qx(1,1,n,1,now - 1),(ll)0)<<std::endl;
ll ans = std::max((std::abs(qx(1,1,n,now,n) - std::min(qi(1,1,n,1,now - 1),(ll)0)) + 1),std::abs(qi(1,1,n,now,n) - std::max(qx(1,1,n,1,now - 1),(ll)0)));
f[now] = ans / 2;
change(1,1,n,e[i].to,n,1);
while(l > i){
change(1,1,n,e[l].to,n,2);
}
}
for(int i = 1;i <= n;++i)
std::cout<<f[i]<<" ";
}