ABC283F暴力构造与时间复杂度线段树

剩下40分钟了，感觉随便打个暴力，不然没提高了……
暴力能不能AC呢？数据随机生成，均摊复杂度能过关吧？能卡吗？构造极端数据试试？让相邻大小数字距离约等于$\sqrt{n}$，最大次数总和约为$n * \sqrt{n}$，交上去，果然AC了！

#include <bits/stdc++.h>
using namespace std;
int n, m, i, j, k, s, a[200005];
int main(){
    scanf("%d", &n);
    for(i=1; i<=n; i++){
        scanf("%d", &a[i]);
    }
    for(i=1; i<=n; i++){
        for(j=1, s=n+n; j<=s; j++){//暴力枚举左右两边
            if(i > j) s = min(s, abs(a[i]-a[i-j])+j);
            if(i+j <= n) s = min(s, abs(a[i]-a[i+j])+j);
        }//距离超过最优值break
        printf("%d ", s);//看样例感觉范围挺小的
    }
    return 0;
}

线段树做法：枚举每个元素a[i]，有左右两边需要查找，做法类似；对于左边情况，有比a[i]大的，也有小的，分开处理就可以去掉绝对值。左边的是a[j]，如果它小，那么就是a[i]-a[j]+i-j，其中a[i]+i不变，用线段树维护-a[j]-j的最小值即可。大的同理。

#include <bits/stdc++.h>
#define N 200005
using namespace std;
int n, m, i, j, k, c, p, q, a[N], v[N];
int d[N*4], lc[N*4], rc[N*4];
void gai(int &p, int l, int r, int k, int x){
    if(!p) p = ++c;
    if(l == r) d[p] = x;//该位置只修改1次
    else{
        int m=l+r>>1;
        if(k <= m) gai(lc[p], l, m, k, x);
        else gai(rc[p], m+1, r, k, x);
        d[p] = min(d[p], x);//维护区间最小值
    }
}
int cha(int p, int l, int r, int x, int y){
    if(!p || x<=l && r<=y) return d[p];
    int m=l+r>>1, s=1e9;
    if(x <= m) s = min(s, cha(lc[p], l, m, x, y));
    if(y > m) s = min(s, cha(rc[p], m+1, r, x, y));
    return s;//查询区间最大值
}
int main(){
    scanf("%d", &n);
    for(i=1; i<=n; i++){
        scanf("%d", &a[i]);
        v[i] = n + n;
    }
    memset(d, 9, sizeof(d));
    for(i=1; i<=n; i++){//处理左边
        v[i] = min(v[i], cha(p, 1, n, 1, a[i]-1)+i+a[i]);
        v[i] = min(v[i], cha(q, 1, n, a[i]+1, n)+i-a[i]);
        gai(p, 1, n, a[i], -a[i]-i);//a[i]大，前面的小
        gai(q, 1, n, a[i], a[i]-i);//a[i]小，前面的大
    }
    memset(d, 9, sizeof(d));
    memset(lc, c=0, sizeof(lc));
    memset(rc, p=q=0, sizeof(rc));
    for(i=n; i>=1; i--){//处理右边，两边取最小值
        v[i] = min(v[i], cha(p, 1, n, 1, a[i]-1)-i+a[i]);
        v[i] = min(v[i], cha(q, 1, n, a[i]+1, n)-i-a[i]);
        gai(p, 1, n, a[i], -a[i]+i);
        gai(q, 1, n, a[i], a[i]+i);
    }
    for(i=1; i<=n; i++) printf("%d ", v[i]);
    return 0;
}