【线段树】【积累】牛客练习赛70 F曲调
题意：
给定一个长度为 (n) 的序列 (a)， (nleq 100000,\,|a_i|leq10^9) ，有 (m) 个询问 。 每个询问给出 (l,r) ，要求区间 ([l,r]) 绝对值最小的子段和（子段不为空）。
叨叨：
打练习赛的时候考虑了用莫队离散，然后用线段树+set查询和修改记录，但是莫队需要维护 (l) 和 (r) ，但是修改会相互影响之前的值，太难实现了。
完全没想到固定一个端点的做法qaq。想到了也想不出题解这种复杂度的做法。
到底还是因为没习惯这种套路。
题解：
对询问以 (r) 递增排序，然后枚举 (r) 来更新以 (r) 为右端点的所有区间的答案。
预先处理数组的前缀和，记为 (sum) 。
对于当前 (x=r) ，求 最大的 (x_1) 满足 (x_1<x) 使得 (sum_{x{1}}leq sum_x) ，然后对满足 (lleq x_1+1) 的 (l) 的更新答案 (min(ans_l,sum_x-sum_{x_1})) ，再求最大的 (x_2) 满足 (x_2<x_1) 使得 (sum_{x_1}leq sum_{x_2}leq sum_x) ，然后对满足 (lleq{x_2+1}) 的 (l) 更新答案 (min(ans_l,sum_x-sum_{x_2}))。按照上面步骤执行下去，直到 (sum_x=sum_{x_i}) 或 (x_i=1) 为止。
此时每个点寻找 (x) 的次数最糟会达 (mathcal{O(n)}) ，需要优化。
可以发现，每当寻找点 (x_i) ，若 (sum_{x_i}-sum_{x_{i-1}}leq sum_x-sum_{xi}) ，则该 (x_i) 对答案无贡献，所以每次可以只寻找满足 (lceilfrac{sum_x+sum_{x_{i-1}}}2 ceilleq sum_{x_i}leq sum_x) 的最大 (x_i) 即可，每次寻找不会超过上一次的一般，总共需要寻找 (mathcal{O}(W)) ， (W) 为 (sum) 的值域。
对于 (sum_{x_1}geq sum_x) 用相同方法再处理一遍。
用主席树寻找 (x_i) ，用线段树维护 (min) ，时间复杂度 (mathcal{O}(n\,logn\,logW)) 。
代码：
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define mkp(a,b) make_pair(a,b)
using namespace std;
typedef long long ll;
const int maxn=5e5+5;
const int inf=0x3f3f3f3f;
const int mod=998244353;
int n,m;
ll h[maxn];int cnt;
inline int id(ll x){return lower_bound(h+1,h+1+cnt,x)-h;}
int a[maxn];ll sum[maxn];
struct Q{
int l,r,id;
bool operator<(const Q&p)const{return r<p.r;}
}q[maxn];
int T[maxn],L[maxn<<2],R[maxn<<2],num[maxn<<2],tnt;
void update(int &rt,int pre,int l,int r,int x)
{
if(!rt||rt==pre){
rt=++tnt;L[rt]=L[pre];R[rt]=R[pre];num[rt]=num[pre];
}
num[rt]++;
if(l==r)return;
int mid=(l+r)>>1;
if(x<=mid)update(L[rt],L[pre],l,mid,x);
else update(R[rt],R[pre],mid+1,r,x);
}
int qma(int rt,int pre,int l,int r,int ql,int qr)
{
if(!(num[rt]-num[pre]))return 0;
if(l==r)return l;
int mid=(l+r)>>1,tres=0;
if(qr>mid&&(num[R[rt]]-num[R[pre]]))tres=qma(R[rt],R[pre],mid+1,r,ql,qr);
if(tres)return tres;
return qma(L[rt],L[pre],l,mid,ql,qr);
}
const ll UP=1e16;
ll mi[maxn<<2],ly[maxn<<2];
void build(int k,int l,int r)
{
ly[k]=UP;
if(l==r){
mi[k]=abs(a[l]);return;
}
int mid=(l+r)>>1;
build(k<<1,l,mid);build(k<<1|1,mid+1,r);
mi[k]=min(mi[k<<1],mi[k<<1|1]);
}
void down(int k)
{
ly[k<<1]=min(ly[k<<1],ly[k]);ly[k<<1|1]=min(ly[k<<1|1],ly[k]);ly[k]=UP;
mi[k<<1]=min(mi[k<<1],ly[k<<1]);mi[k<<1|1]=min(mi[k<<1|1],ly[k<<1|1]);
}
void update(int k,int l,int r,int ql,int qr,ll v)
{
if(ql>r||qr<l)return;
if(ql<=l&&r<=qr){
mi[k]=min(mi[k],v);ly[k]=min(ly[k],v);
return;
}
if(ly[k]!=UP)down(k);
int mid=(l+r)>>1;
update(k<<1,l,mid,ql,qr,v);update(k<<1|1,mid+1,r,ql,qr,v);
mi[k]=min(mi[k<<1],mi[k<<1|1]);
}
ll query(int k,int l,int r,int ql,int qr)
{
if(ql>r||qr<l)return UP;
if(ql<=l&&r<=qr)return mi[k];
if(ly[k]!=UP)down(k);
int mid=(l+r)>>1;
return min(query(k<<1,l,mid,ql,qr),query(k<<1|1,mid+1,r,ql,qr));
}
void solve(int r)
{
ll sr=sum[r],sl=h[1];int t,rr=r;
update(1,1,n,1,1,abs(sr));
while(sr>sl&&rr>1)
{
t=qma(T[id(sr)],T[id(sl)-1],1,n,1,rr-1);
// printf("(%lld %lld %d %d %lld) ",sl,sr,rr,t,sum[t]);
if(!t)break;
sl=sum[t];rr=t;
update(1,1,n,1,t+1,sr-sl);
sl=(sl+sr+1)>>1;
}
sr=sum[r];sl=h[cnt];rr=r;
while(sr<sl&&rr>1)
{
t=qma(T[id(sl)],T[id(sr)-1],1,n,1,rr-1);
// printf("(%lld %lld %d %d %lld) ",sl,sr,rr,t,sum[t]);
if(!t)break;
sl=sum[t];rr=t;
update(1,1,n,1,t+1,sl-sr);
sl=(sl+sr+1)>>1;
}
}
struct TT{
ll v;int id;
bool operator<(const TT&p)const{return v<p.v;}
}pt[maxn];
ll res[maxn];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
sum[i]=sum[i-1]+a[i];
h[++cnt]=sum[i];
pt[i]={sum[i],i};
}
build(1,1,n);
sort(h+1,h+1+cnt);
cnt=unique(h+1,h+1+cnt)-h-1;
sort(pt+1,pt+1+n);
for(int i=1,idd;i<=n;i++){
idd=id(pt[i].v);
update(T[idd],T[idd-1],1,n,pt[i].id);
}
for(int i=1,l,r;i<=m;i++)
{
scanf("%d%d",&l,&r);
q[i]={l,r,i};
}
sort(q+1,q+1+m);
int st=0;
for(int i=1;i<=m;i++)
{
while(st<q[i].r)solve(++st);
res[q[i].id]=query(1,1,n,q[i].l,q[i].r);
}
for(int i=1;i<=m;i++)printf("%lld
",res[i]);
}