sequence

Posted on | In , , ,

题目链接

题意

有两个序列$a, b$。
计算

思路

单调栈

枚举每个数字的贡献，我们就要计算出产生作用的区间，用单调栈可以扫两遍处理。
在这个区间里()数字是最小的。

线段树或ST表

我们记表示。
若，那么我们要找，也就是。
只要找到就可以了。
若可以类似处理。
用ST表或线段树处理区间最大或最小值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include<bits/stdc++.h>
using namespace std;
#define lson rt<<1
#define rson rt<<1|1
#define Lson L,mid,lson
#define Rson mid+1,R,rson
const int maxn=3e6+10;
typedef long long ll;
ll tree[maxn*4];
ll tree2[maxn*4];
ll a[maxn*4];
ll sum[maxn];
int stk[maxn];
int Left[maxn],Right[maxn];
void pushup(int rt)
{
    tree[rt]=max(tree[lson],tree[rson]);
    tree2[rt]=min(tree2[lson],tree2[rson]);
    //printf("tree %lld %lld\n", tree[rt], tree2[rt]);
}
void build(int L,int R,int rt)
{
    if(L==R)
    {
        tree[rt]=sum[L];
        tree2[rt]=sum[L];
        // printf("build end %lld %lld\n", tree[rt], tree2[rt]);
        return;
    }
    int mid=(L+R)>>1;
    build(Lson);
    build(Rson);
    pushup(rt);
    // printf("build %d %d %lld %lld\n", L, R, tree[rt], tree2[rt]);
}
ll query1(int l,int r,int L,int R,int rt)
{
    if(l<=L&&r>=R)
    {
        // printf("%d %d %lld\n", L, R, tree[rt]);
        return tree[rt];
    }
    int mid=(L+R)>>1;
    ll res=-1e15;
    if(l<=mid)
        res=max(res,query1(l,r,Lson));
    if(r>mid)
        res=max(res,query1(l,r,Rson));
    return res;
}
ll query2(int l,int r,int L,int R,int rt)
{
    if(l<=L&&r>=R)
    {
        return tree2[rt];
    }
    int mid=(L+R)>>1;
    ll res=1e15;
    if(l<=mid)
        res=min(res,query2(l,r,Lson));
    if(r>mid)
        res=min(res,query2(l,r,Rson));
    return res;
}
ll b[maxn];
int main()
{
    int N;
    scanf("%d",&N);
    for(int i=1;i<=N;i++)
    {
        scanf("%lld",&b[i]);
        //sum[i]=sum[i-1]+a[i];
        // printf("sum %d  %lld\n", i, sum[i]);
        //cout<<sum[i]<<endl;
    }
    for (int i = 1; i <= N; i++)
    {
        scanf("%lld", &a[i]);
        sum[i]=sum[i - 1] + a[i];  
    }
    build(1,N,1);
    int top=-1;
    for(int i=1;i<=N;i++)
    {
        while(top!=-1&&b[stk[top]]>b[i])
            Right[stk[top--]] = i - 1;
            /*
        if(top==-1)
            Left[i]=i;
        else
            Left[i]=stk[top]+1;
            */
        stk[++top]=i;
    }
    while (top != -1)
    {
        Right[stk[top--]] = N;
    }
    top=-1;
    for(int i=N;i>=1;i--)
    {
        while(top!=-1&&b[stk[top]]>b[i])
        {
            //cout<<i<<" "<<top<<endl;
            Left[stk[top--]] = i + 1;
        }
        /*
        if(top==-1)
            Left[i]=i;
        else
            Left[i]=stk[top]-1;
        */
        stk[++top]=i;
    }
    while (top != -1)
    {
        Left[stk[top--]] = 1;
    }
/* 
    for(int i=1;i<=N;i++)
        cout<<Left[i]<<" "<<Right[i]<<endl;
    */
    // printf("fuck %d %d\n", Left[3], Right[3]);
    // printf("%lld %lld ** ?? \n", query1(Left[3], 3 - 1, 1, N, 1), query2(3, Right[3], 1, N, 1));
    ll ans=0;
    for(int i=1;i<=N;i++)
    {
        if(b[i]>=0)
            ans=max(ans,b[i]*(sum[Right[i]]-sum[Left[i]-1]));
        else
        {
            if (Left[i] == i && Right[i] == i)
            {
                ans = max(ans, b[i] * 1ll * b[i]);
            }
            else if(Left[i]==i)
            {
               //  cout<<query2(i,Right[i],1,N,1)<<endl;
                ans=max(ans,b[i]*(query2(i,Right[i],1,N,1)-sum[i] + a[i]));
            }
            else if(Right[i]==i){
                ans=max(ans,b[i]*(sum[i-1]-query1(Left[i],i-1,1,N,1) + a[i]));
                ans = max(ans, b[i] * (sum[i - 1] - sum[Left[i] - 1] + a[i]));
            }
            else{
                ans=max(ans,b[i]*(sum[i-1]-query1(Left[i],i-1,1,N,1)+query2(i,Right[i],1,N,1)-sum[i]+a[i]));
                ans = max(ans, b[i] * (sum[i - 1] - sum[Left[i] - 1] + query2(i, Right[i], 1, N, 1) - sum[i] + a[i]));
                // printf("%d %lld %lld ?????\n", i, query1(Left[i] - 1, i - 1, 1, N, 1), query2(i, Right[i], 1, N, 1));
            }
            // cout<<ans<<endl;
        }
    }
    printf("%lld\n",ans);
    return 0;
}

另一个思路

先$O(n)$建出笛卡尔树（单调栈），每个点都在它和子树的区间有作用。
我们递归地处理每个点表示的区间的左最大、左最小、右最大和右最小（像线段树区间合并问题那样那样）。然后就可以更新答案了。
复杂度更低一点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#ifndef ONLINE_JUDGE
#define dbg(x...) do{cout << "\033[33;1m" << #x << "->" ; err(x);} while (0)
void err(){cout << "\033[39;0m" << endl;}
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x){for (auto v: a) cout << v << ' '; err(x...);}
template<typename T, typename... A>
void err(T a, A... x){cout << a << ' '; err(x...);}
#else
#define dbg(...)
#endif
#define inf 1ll << 50
const int N = 3e6 + 5;
 
#define ls(x) treap[x].child[0]
#define rs(x) treap[x].child[1]
 
struct node
{
    int child[2];
    ll val;
    int size;
    ll lmin, rmin, lmax, rmax;
    int len[4];
}treap[N];
 
int a[N], b[N];
int root;
int top, fjw[N];
ll ans = 0;
 
void push_up(int rt)
{
    treap[rt].size = treap[ls(rt)].size + treap[rs(rt)].size + 1;
    treap[rt].val += treap[ls(rt)].val + treap[rs(rt)].val;
    treap[rt].lmin = treap[ls(rt)].lmin;
    treap[rt].len[0] = treap[ls(rt)].len[0];
    //if (treap[ls(rt)].len[0] == treap[ls(rt)].size)
    //{
        /*
        if (treap[rt].lmin > treap[ls(rt)].lmin + b[rt])
        {
            treap[rt].lmin = treap[ls(rt)].lmin + b[rt];
            treap[rt].len[0]++;
        }
        */
    if (treap[rt].lmin > treap[ls(rt)].val + b[rt] + treap[rs(rt)].lmin)
    {
        treap[rt].lmin = treap[ls(rt)].val + b[rt] + treap[rs(rt)].lmin;
        treap[rt].len[0] = treap[ls(rt)].size + 1 + treap[rs(rt)].len[0];
    }
    //}
    treap[rt].lmax = treap[ls(rt)].lmax;
    treap[rt].len[1] = treap[ls(rt)].len[1];
    //if (treap[ls(rt)].len[1] == treap[ls(rt)].size)
    //{
        /*
        if (treap[rt].lmax < treap[ls(rt)].lmax + b[rt])
        {
            treap[rt].lmax = treap[ls(rt)].lmax + b[rt];
            treap[rt].len[1]++;
        }
        */
    if (treap[rt].lmax < treap[ls(rt)].val + b[rt] + treap[rs(rt)].lmax)
    {
        treap[rt].lmax = treap[ls(rt)].val + b[rt] + treap[rs(rt)].lmax;
        treap[rt].len[1] = treap[ls(rt)].size + 1 + treap[rs(rt)].len[1];
    }
    //}
     
    treap[rt].rmin = treap[rs(rt)].rmin;
    treap[rt].len[2] = treap[rs(rt)].len[2];
    //if (treap[rs(rt)].len[2] == treap[rs(rt)].size)
    //{
        /*
        if (treap[rt].rmin > treap[rs(rt)].rmin + b[rt])
        {
            treap[rt].rmin = treap[rs(rt)].rmin + b[rt];
            treap[rt].len[2]++;
        }
        */
    if (treap[rt].rmin > treap[rs(rt)].val + b[rt] + treap[ls(rt)].rmin)
    {
        treap[rt].rmin = treap[rs(rt)].val + b[rt] + treap[ls(rt)].rmin;
        treap[rt].len[2] = treap[rs(rt)].size + 1 + treap[ls(rt)].len[2];
    }
    //}
     
    treap[rt].rmax = treap[rs(rt)].rmax;
    treap[rt].len[3] = treap[rs(rt)].len[3];
//  if (treap[rs(rt)].len[3] == treap[rs(rt)].size)
//  {
        /*
        if (treap[rt].rmax < treap[rs(rt)].lmin + b[rt])
        {
            treap[rt].lmin = treap[ls(rt)].lmin + b[rt];
            treap[rt].len[0]++;
        }
        */
//      dbg(rt, rs(rt), b[rt], treap[rt].rmax, treap[rs(rt)].rmax);
    if (treap[rt].rmax < treap[rs(rt)].val + b[rt] + treap[ls(rt)].rmax)
    {
        treap[rt].rmax = treap[rs(rt)].val + b[rt] + treap[ls(rt)].rmax;
        treap[rt].len[3] = treap[rs(rt)].size + 1 + treap[ls(rt)].len[3];
    }
//  }
}
 
void dfs(int u)
{
    if (!u)
        return;
    //dbg(u, ls(u), rs(u));
    dfs(ls(u));
    dfs(rs(u));
    if (a[u] >= 0)
        ans = max(ans, a[u] * (b[u] + treap[ls(u)].rmax + treap[rs(u)].lmax));
    else
        ans = max(ans, a[u] * (b[u] + treap[ls(u)].rmin + treap[rs(u)].lmin));
    push_up(u);
    //dbg(u, treap[u].lmin, treap[u].lmax, treap[u].rmin, treap[u].rmax, ans);
}
 
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++)
        scanf("%d", &b[i]);
    top = 0;
    for (int i = 1; i <= n; i++)
    {
        rs(i) = ls(i) = 0;
        treap[i].val = b[i];
        while (top >= 1 && a[fjw[top]] >= a[i])
        {
            ls(i) = fjw[top];
            top--;
        }
        if (top >= 1)
            rs(fjw[top]) = i;
        else
            root = i;
        fjw[++top] = i;
    }
    ans = -1e15;
    dfs(root);
    printf("%lld\n", ans);
    return 0;
}

0%