2019CSUST集训队选拔赛题解（一）

来自ppq的毒瘤线段树

Sneakers

Description

有一天喜欢买鞋的ppq和小伙伴来到了某一家球鞋店，球鞋店有n种球鞋，价格分别为ai，ppq在鞋店兜兜转转，发现鞋店老板会偶尔将某段区间内球鞋的价格增加或减少，或者将某双球鞋的价格由价格A修改至价格B，机智的ppq将这些信息记录下来，可是ppq不会数数，所以他向机智的ACMer们求助，请帮助ppq完成以下m次操作，并得到ppq询问的结果。

有以下6种操作：

操作1：鞋店老板将下标位于【L，R】区间的球鞋的价格增加k。（无良老板）

操作2：鞋店老板将下标位于【L，R】区间的球鞋的价格减少k。（良心老板）

操作3：鞋店老板将下标为pos的球鞋的价格修改为bi

操作4：ppq想买下标位于【L，R】区间内最贵的球鞋，询问他需要花费多少钱

操作5：ppq想买下标位于【L，R】区间内最便宜的球鞋，询问他需要花费多少钱

操作6：ppq想买下标位于【L，R】区间内所有的球鞋，询问他需要花费多少钱

Input

第一行输入n和q（n∈[1,300000],q∈[1,300000]）

接下来一行n个数ai,表示第i种球鞋的价格，(ai∈[0,100000]) (因为可能是限量球鞋所以特别贵，滑稽)

接下来q行操作：

q1 L R k 表示将区间[L,R] 内的球鞋价格增加k元 (k∈[0,100000]，1<=L<R<=n)

q2 L R k 表示将区间[L,R]内的球鞋价格减少k元 (k∈[0,100000],1<=L<R<=n)

q3 pos b表示将第pos双鞋的价格修改为b (pos∈[1,n],b∈[0,1000000],1<=pos<=n)

q4 L R 表示询问区间[L,R]内最贵的球鞋(1<=L<R<=n)

q5 L R 表示询问区间[L,R]内最便宜的球鞋(1<=L<R<=n)

q6 L R表示询问区间[L,R]内球鞋的价格之和(1<=L<R<=n)

Output

输出每次询问的答案（请注意答案可能为负数）

记得push_down ! ! !

ACODE:

//

#include<stdio.h>

#include<iostream>

#include<string.h>

#include<algorithm>

#include<math.h>

#include<string>

#include<queue>

#include<utility>

#include<vector>

#define lson l , m , rt << 1

#define rson m+1 , r , rt << 1 | 1

#define mem(a,b) memset(a,b,sizeof(a))

using namespace std;

typedef long long ll;

const double pi = 3.1415926535;

const double eps = 1e-;

const int MX = 1e6 + ;

const int maxbit = ;

const double val = pi/180.0;

const int INF = 0x3f3f3f3f;

const ll LINF = 0x3f3f3f3f3f3f3f3f;

ll n,m;

struct node

{

    ll sum;

    ll max;

    ll min;

}t[MX<<];

ll a[MX<<];

ll tag[MX<<];

inline ll ls(ll p){return p << ;}

inline ll rs(ll p){return p << |;}

void push_up(ll p)

{

    t[p].min = min(t[ls(p)].min,t[rs(p)].min);

    t[p].sum = t[ls(p)].sum + t[rs(p)].sum;

    t[p].max = max(t[ls(p)].max,t[rs(p)].max);

}

void build(ll p,ll l,ll r)

{

    if(l == r)

    {

        t[p].max = a[l];

        t[p].min = a[l];

        t[p].sum = a[l];

        return;

    }

    ll mid = (l+r) >> ;

    build(ls(p),l,mid);

    build(rs(p),mid+,r);

    push_up(p);

}

inline void f(ll p,ll l,ll r,ll k)

{

    tag[p] = tag[p] + k;

    t[p].sum = t[p].sum + (r - l + )*k;

    t[p].min =t[p].min+k;

    t[p].max =t[p].max+k;

}

inline void push_down(ll p,ll l,ll r)

{

    ll mid = (l+r) >> ;

    f(ls(p),l,mid,tag[p]);

    f(rs(p),mid+,r,tag[p]);

    tag[p] = ;

}

inline void update1(ll L,ll R,ll l,ll r,ll p,ll k)

{

    //printf("***\n");

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

    {

        t[p].sum+=k*(r - l + );

        t[p].max +=k;

        t[p].min +=k;

        tag[p]+=k;

        return;

    }

    push_down(p,l,r);

    ll mid = (l + r) >> ;

    if(L <= mid ) update1(L,R,l,mid,ls(p),k);

    if(R > mid) update1(L,R,mid+,r,rs(p),k);

    push_up(p);

}

inline void update2(ll p,ll l,ll r,ll k,ll tar)

{

    if(r == l)

    {

        t[p].min = k;

        t[p].max = k;

        t[p].sum = k;

        return;

    }

    ll mid = (l + r) >> ;

    push_down(p,l,r);

    if(tar > mid ) update2(rs(p),mid + ,r,k,tar);

    else update2(ls(p),l,mid,k,tar);

    push_up(p);

}

ll query1(ll L,ll R,ll l,ll r,ll p)

{

    ll ans = ;

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

        return t[p].sum;

    ll mid = (l + r) >> ;

    push_down(p,l,r);

    if(L <= mid) ans +=query1(L,R,l,mid,ls(p));

    if(R > mid) ans +=query1(L,R,mid+,r,rs(p));

    return ans;

}

ll query2(ll L,ll R,ll l,ll r,ll p)

{

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

    {

        return t[p].max;

    }

    push_down(p,l,r);

    ll ans = - LINF;

    ll mid = (l + r) >> ;

    if(L <= mid)

    {

        ans = max(ans,query2(L,R,l,mid,ls(p)));

    }

    if(R > mid)

    {

        ans = max(ans,query2(L,R,mid + ,r,rs(p)));

    }

    return ans;

}

ll query3(ll L,ll R,ll l,ll r,ll p)

{

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

        return t[p].min;

    push_down(p,l,r);

    ll ans = LINF;

    ll mid = (l + r) >> ;

    if(L <= mid)

        ans = min(ans,query3(L,R,l,mid,ls(p)));

    if(R > mid)

        ans = min(ans,query3(L,R,mid+,r,rs(p)));

    return ans;

}

int main(int argc, char const *argv[])

{

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

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

        scanf("%lld",&a[i]);

    char op[];

    ll L,R,k,pos;

    build(,,n);

    while(m--)

    {

        scanf(" %s",op);

        if(op[] == '')

        {

            scanf("%lld%lld%lld",&L,&R,&k);

            update1(L,R,,n,,k);

        }

        else if(op[] == '')

        {

            scanf("%lld%lld%lld",&L,&R,&k);

            k = -k;

            update1(L,R,,n,,k);

        }

        else if(op[] == '')

        {

            scanf("%lld%lld",&pos,&k);

            update2(,,n,k,pos);

        }

        else if(op[] == '')

        {

            scanf("%lld%lld",&L,&R);

            printf("%lld\n",query2(L,R,,n,));

        }

        else if(op[] == '')

        {

            scanf("%lld%lld",&L,&R);

            printf("%lld\n",query3(L,R,,n,));

        }

        else{

            scanf("%lld%lld",&L,&R);

            printf("%lld\n",query1(L,R,,n,));

        }

    }

    return ;

}

以后千万不能带个错误的线段树板子了

巴特西

2019CSUST集训队选拔赛题解（一）

最新文章

热门文章