Description：

Solution：

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 600010

typedef long long ll;

struct query

{

    int t,tp,p;

    ll v;

}q[MAXN];

int s[MAXN];

ll pos[MAXN],spe[MAXN];

int last[MAXN];

struct line

{

    ll k,b;

    line(ll k_ = 0,ll b_ = 0){k = k_;b = b_;}

    ll f(ll x){return k * x + b;}

};

#define INFLL 0x3f3f3f3f3f3f3f3f

#define INF 0x3f3f3f3f

struct node

{

    int lc,rc;

    line lx,ln;

    node(){lx.k = ln.k = 0;lx.b = -INFLL;ln.b = INFLL;}

}t[MAXN << 1];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

#define mid ((l + r) >> 1)

void build(int &rt,int l,int r)

{

    rt = newnode();

    if(l == r)return;

    build(t[rt].lc,l,mid);

    build(t[rt].rc,mid + 1,r);

    return;

}

void add1(int rt,int L,int R,line k,int l,int r)

{

    if(L <= l && r <= R)

    {

        if(t[rt].lx.f(s[l]) >= k.f(s[l]) && t[rt].lx.f(s[r]) >= k.f(s[r]));

        else if(t[rt].lx.f(s[l]) < k.f(s[l]) && t[rt].lx.f(s[r]) < k.f(s[r]))t[rt].lx = k;

        else

        {

            int mi = s[mid];

            if(t[rt].lx.f(mi) < k.f(mi))swap(t[rt].lx,k);

            if(k.f(s[l]) > t[rt].lx.f(s[l]))add1(t[rt].lc,l,mid,k,l,mid);

            else add1(t[rt].rc,mid + 1,r,k,mid + 1,r);

        }

        return;

    }

    if(L <= mid)add1(t[rt].lc,L,R,k,l,mid);

    if(R > mid)add1(t[rt].rc,L,R,k,mid + 1,r);

    return;

}

void add2(int rt,int L,int R,line k,int l,int r)

{

    if(L <= l && r <= R)

    {

        if(t[rt].ln.f(s[l]) <= k.f(s[l]) && t[rt].ln.f(s[r]) <= k.f(s[r]));

        else if(t[rt].ln.f(s[l]) > k.f(s[l]) && t[rt].ln.f(s[r]) > k.f(s[r]))t[rt].ln = k;

        else

        {

            int mi = s[mid];

            if(t[rt].ln.f(mi) > k.f(mi))swap(t[rt].ln,k);

            if(k.f(s[l]) < t[rt].ln.f(s[l]))add2(t[rt].lc,l,mid,k,l,mid);

            else add2(t[rt].rc,mid + 1,r,k,mid + 1,r);

        }

        return;

    }

    if(L <= mid)add2(t[rt].lc,L,R,k,l,mid);

    if(R > mid)add2(t[rt].rc,L,R,k,mid + 1,r);

    return;

}

ll query(int rt,int p,int l,int r)

{

    ll res = max(t[rt].lx.f(s[p]),-t[rt].ln.f(s[p]));

    if(l == r)return res;

    if(p <= mid)res = max(res,query(t[rt].lc,p,l,mid));

    else res = max(res,query(t[rt].rc,p,mid + 1,r));

    return res;

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i = 1;i <= n;++i)scanf("%lld",&pos[i]);

    for(int i = 1;i <= n;++i)last[i] = 1;

    string c;

    for(int i = 1;i <= m;++i)

    {

        scanf("%d",&q[i].t);

        cin >> c;

        if(c[0] == 'q')q[i].tp = 0;

        else q[i].tp = 1,scanf("%d%lld",&q[i].p,&q[i].v);

        s[i] = q[i].t;

    }

    s[s[0] = m + 1] = -INF;s[++s[0]] = INF;

    sort(s + 1,s + 1 + s[0]);

    s[0] = unique(s + 1,s + 1 + s[0]) - s - 1;

    build(root,1,s[0]);

    for(int i = 1;i <= m;++i)

    {

        if(q[i].tp == 1)

        {

            int cur = lower_bound(s + 1,s + 1 + s[0],q[i].t) - s;

            ll k = spe[q[i].p],b = pos[q[i].p] - spe[q[i].p] * s[last[q[i].p]];

            add1(root,last[q[i].p],cur,(line){k,b},1,s[0]);

            add2(root,last[q[i].p],cur,(line){k,b},1,s[0]);

            last[q[i].p] = cur;

            pos[q[i].p] = k * s[cur] + b;

            spe[q[i].p] = q[i].v;

        }

    }

    for(int i = 1;i <= n;++i)

    {

        ll k = spe[i],b = pos[i] - spe[i] * s[last[i]];

        add1(root,last[i],s[0],(line){k,b},1,s[0]);

        add2(root,last[i],s[0],(line){k,b},1,s[0]);

    }

    for(int i = 1;i <= m;++i)

    {

        if(q[i].tp == 0)

        {

            int cur = lower_bound(s + 1,s + 1 + s[0],q[i].t) - s;

            printf("%lld\n",query(root,cur,1,s[0]));

        }

    }

    return 0;

}