1. 题目

传送门= ̄ω ̄=

有n个数和5种操作

add a b c:把区间[a,b]内的所有数都增加c

set a b c:把区间[a,b]内的所有数都设为c

sum a b:查询区间[a,b]的区间和

max a b:查询区间[a,b]的最大值

min a b:查询区间[a,b]的最小值

2. 题解

好好打线段树就行了
如果来了个set,add就没了,add的标记直接清空为0
如果来了个add,如果set没有标记,就add的标记增加,否则set的标记增加

注意数据中有个点是全set为0,所以要专门写个标记,标记set是否被标记了,不能直接判断set标记是否为0

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
struct N
{
    LL l,r,sum,max,min,pf,cf;bool book;N*s[2];
    N(){l=r=sum=max=min=pf=cf=book=0,s[0]=s[1]=0;}
}*root=0;
void update(N*&a)
{
    a->sum=a->s[0]->sum+a->s[1]->sum;
    a->max=max(a->s[0]->max,a->s[1]->max);
    a->min=min(a->s[0]->min,a->s[1]->min);
}
void pdown(N*&a)
{
    if(a->book)
    {
        a->s[0]->sum=(a->s[0]->r-a->s[0]->l+1)*a->cf;
        a->s[1]->sum=(a->s[1]->r-a->s[1]->l+1)*a->cf;
        a->s[0]->max=a->s[0]->min=a->s[1]->max=a->s[1]->min=a->cf;
        a->s[0]->cf=a->s[1]->cf=a->cf,a->s[0]->pf=a->s[1]->pf=0;
        a->s[0]->book=a->s[1]->book=1;
    }
    else
    {
        a->s[0]->sum+=(a->s[0]->r-a->s[0]->l+1)*a->pf;
        a->s[1]->sum+=(a->s[1]->r-a->s[1]->l+1)*a->pf;
        a->s[0]->max+=a->pf,a->s[0]->min+=a->pf;
        a->s[1]->max+=a->pf,a->s[1]->min+=a->pf;
        if(a->s[0]->cf)a->s[0]->cf+=a->pf;else a->s[0]->pf+=a->pf;
        if(a->s[1]->cf)a->s[1]->cf+=a->pf;else a->s[1]->pf+=a->pf;
    }
    a->cf=a->pf=a->book=0;
}
void build(LL l,LL r,N*&a)
{
    a=new N,a->l=l,a->r=r;
    if(l==r){scanf("%lld",&a->sum),a->max=a->min=a->sum;return;}
    build(l,(l+r)>>1,a->s[0]),build(((l+r)>>1)+1,r,a->s[1]),update(a);
}
void add(LL l,LL r,LL k,N*&a)
{
    if(l<=a->l&&a->r<=r)
    {
        a->sum+=(a->r-a->l+1)*k,a->min+=k,a->max+=k;
        if(a->book)a->cf+=k;else a->pf+=k;
        return;
    }
    if(a->book||a->pf)pdown(a);
    if(l<=((a->l+a->r)>>1))add(l,r,k,a->s[0]);
    if(r>((a->l+a->r)>>1))add(l,r,k,a->s[1]);
    update(a);
}
void change(LL l,LL r,LL k,N*&a)
{
    if(l<=a->l&&a->r<=r)
    {a->sum=(a->r-a->l+1)*k,a->min=k,a->max=k,a->pf=0,a->cf=k,a->book=1;return;}
    if(a->book||a->pf)pdown(a);
    if(l<=((a->l+a->r)>>1))change(l,r,k,a->s[0]);
    if(r>((a->l+a->r)>>1))change(l,r,k,a->s[1]);
    update(a);
}
LL query_sum(LL l,LL r,N*&a)
{
    if(l<=a->l&&a->r<=r)return a->sum;
    if(a->book||a->pf)pdown(a);
    LL tot=0;
    if(l<=((a->l+a->r)>>1))tot+=query_sum(l,r,a->s[0]);
    if(r>((a->l+a->r)>>1))tot+=query_sum(l,r,a->s[1]);
    return tot;
}
LL query_min(LL l,LL r,N*&a)
{
    if(l<=a->l&&a->r<=r)return a->min;
    if(a->book||a->pf)pdown(a);
    LL tot=LLONG_MAX;
    if(l<=((a->l+a->r)>>1))tot=min(tot,query_min(l,r,a->s[0]));
    if(r>((a->l+a->r)>>1))tot=min(tot,query_min(l,r,a->s[1]));
    return tot;
}
LL query_max(LL l,LL r,N*&a)
{
    if(l<=a->l&&a->r<=r)return a->max;
    if(a->book||a->pf)pdown(a);
    LL tot=LLONG_MIN;
    if(l<=((a->l+a->r)>>1))tot=max(tot,query_max(l,r,a->s[0]));
    if(r>((a->l+a->r)>>1))tot=max(tot,query_max(l,r,a->s[1]));
    return tot;
}
LL n,m;
char opt[10];
int main()
{
    scanf("%lld%lld",&n,&m),build(1,n,root);
    for(LL i=1,a,b,c;i<=m;i++)
    {
        scanf("%s%lld%lld",opt,&a,&b);
        if(!strcmp(opt,"add"))scanf("%lld",&c),add(a,b,c,root);
        else if(!strcmp(opt,"set"))scanf("%lld",&c),change(a,b,c,root);
        else if(!strcmp(opt,"sum"))printf("%lld\n",query_sum(a,b,root));
        else if(!strcmp(opt,"min"))printf("%lld\n",query_min(a,b,root));
        else printf("%lld\n",query_max(a,b,root));
    }
    return 0;
}
分类: 所有

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *