bzoj #6029.「雅礼集训 2017 Day1」市场 线段树

题意

给一个长度为n的序列，要求资瓷区间加，区间整除和求区间最小值，区间和。

n,q≤105 n , q ≤ 10 5

分析

唯一要考虑的就是怎么对区间整除打标记。

如果这个区间的所有数在操作后的增量都是相同的，那么我们就可以对区间打上加标记。判断增量是否相同，只要判断最大值和最小值的增量是否相同即可。

复杂度什么的根本不会证。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ls d<<1
#define rs d<<1|1

typedef long long LL;

const int N=;

int n,m,a[N];
struct tree{int len;LL s,mn,mx,tag;}t[N*];

int read()
{
    int x=,f=;char ch=getchar();
    while (ch<'0'||ch>'9'){if(ch=='-')f=-;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*+ch-'0';ch=getchar();}
    return x*f;
}

void updata(int d)
{
    t[d].s=t[ls].s+t[rs].s;
    t[d].mn=std::min(t[ls].mn,t[rs].mn);
    t[d].mx=std::max(t[ls].mx,t[rs].mx);
}

LL divi(LL x,LL y)
{
    return floor((double)x/y);
}

void mark(int d,LL w)
{
    t[d].tag+=w;t[d].mx+=w;t[d].mn+=w;
    t[d].s+=(LL)w*t[d].len;
}

void pushdown(int d)
{
    if (t[d].tag)
    {
        LL w=t[d].tag;t[d].tag=;
        mark(ls,w);mark(rs,w);
    }
}

void build(int d,int l,int r)
{
    t[d].len=r-l+;
    if (l==r) {t[d].s=t[d].mn=t[d].mx=a[l];return;}
    int mid=(l+r)/;
    build(d*,l,mid);build(d*+,mid+,r);
    updata(d);
}

void add(int d,int l,int r,int x,int y,int z)
{
    if (l<r) pushdown(d);
    if (x<=l&&r<=y) {mark(d,z);return;}
    int mid=(l+r)/;
    if (x<=mid) add(ls,l,mid,x,y,z);
    if (y>mid) add(rs,mid+,r,x,y,z);
    updata(d);
}

void modify(int d,int l,int r,int x,int y,int z)
{
    if (l<r) pushdown(d);
    if (x<=l&&r<=y&&t[d].mx-divi(t[d].mx,z)==t[d].mn-divi(t[d].mn,z))
        {mark(d,-t[d].mx+divi(t[d].mx,z));return;}
    int mid=(l+r)/;
    if (x<=mid) modify(ls,l,mid,x,y,z);
    if (y>mid) modify(rs,mid+,r,x,y,z);
    updata(d);
}

int query1(int d,int l,int r,int x,int y)
{
    if (l<r) pushdown(d);
    if (x<=l&&r<=y) return t[d].mn;
    int mid=(l+r)/;
    if (y<=mid) return query1(ls,l,mid,x,y);
    else if (x>mid) return query1(rs,mid+,r,x,y);
    else return std::min(query1(ls,l,mid,x,y),query1(rs,mid+,r,x,y));
}

LL query2(int d,int l,int r,int x,int y)
{
    if (l<r) pushdown(d);
    if (x<=l&&r<=y) return t[d].s;
    int mid=(l+r)/;
    if (y<=mid) return query2(ls,l,mid,x,y);
    else if (x>mid) return query2(rs,mid+,r,x,y);
    else return query2(ls,l,mid,x,y)+query2(rs,mid+,r,x,y);
}

int main()
{
    n=read();m=read();
    for (int i=;i<=n;i++) a[i]=read();
    build(,,n);
    while (m--)
    {
        int op=read(),l=read()+,r=read()+;
        if (op==)
        {
            int c=read();
            add(,,n,l,r,c);
        }
        else if (op==)
        {
            int d=read();
            modify(,,n,l,r,d);
        }
        else if (op==) printf("%d\n",query1(,,n,l,r));
        else printf("%lld\n",query2(,,n,l,r));
    }
    return ;
}