文档章节

loj #6029. 「雅礼集训 2017 Day1」市场

o
 osc_x4h57ch8
发布于 2018/04/24 08:08
字数 1586
阅读 0
收藏 0

精选30+云产品,助力企业轻松上云!>>>

#6029. 「雅礼集训 2017 Day1」市场

 

题目描述

从前有一个贸易市场,在一位执政官到来之前都是非常繁荣的,自从他来了之后,发布了一系列奇怪的政令,导致贸易市场的衰落。

有 n nn 个商贩,从 0∼n−1 0 \sim n - 10n1 编号,每个商贩的商品有一个价格 ai a_iai​​,有两种政令:

  1. l,r,c l, r, cl,r,c,对于 i∈[l,r],ai←ai+c i \in [l, r], a_i \leftarrow a_i + ci[l,r],ai​​ai​​+c
  2. l,r,d l, r, dl,r,d,对于 i∈[l,r],ai←⌊ai/d⌋ i \in [l, r], a_i \leftarrow \lfloor {a_i}/{d} \rfloori[l,r],ai​​ai​​/d

现在有一个外乡的旅客想要了解贸易市场的信息,有两种询问方式:

  1. 给定 l,r l, rl,r,求 mini∈[l,r]ai \min_{i \in [l, r]} a_imini[l,r]​​ai​​
  2. 给定 l,r l, rl,r,求 ∑i∈[l,r]ai \sum_{i\in [l, r]} a_ii[l,r]​​ai​​

输入格式

第一行为两个空格隔开的整数 n,q n, qn,q 分别表示商贩个数和政令 + 询问个数。
第二行包含 n nn 个由空格隔开的整数 a0∼an−1 a_0 \sim a_{n - 1}a0​​an1​​
接下来 q qq 行,每行表示一个操作,第一个数表示操作编号 1∼4 1 \sim 414,接下来的输入和问题描述一致。

输出格式

对于每个 3、4 操作,输出询问答案。

样例

样例输入

10 10
-5 -4 -3 -2 -1 0 1 2 3 4
1 0 4 1
1 5 9 1
2 0 9 3
3 0 9
4 0 9
3 0 1
4 2 3
3 4 5
4 6 7
3 8 9

样例输出

-2
-2
-2
-2
0
1
1

数据范围与提示

对于 30% 30\%30% 的数据,n,q≤103 n, q \leq 10 ^ 3n,q103​​;
对于 60% 60\%60% 的数据,保证数据随机;
对于 100% 100\%100% 的数据,1≤n,q≤105,0≤l≤r≤n−1,c∈[−104,104],d∈[2,109] 1 \leq n, q \leq 10 ^ 5, 0 \leq l \leq r \leq n - 1, c \in [-10 ^ {4}, 10 ^ 4], d \in [2, 10 ^ 9]1n,q105​​,0lrn1,c[104​​,104​​],d[2,109​​]

 

 区间除用到了分块除法,可以转化为区间加法(复杂度玄学)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define maxn 100010
using namespace std;
int n,m;
long long sum[maxn*10],a[maxn],mn[maxn*10];
long long qread(){
    int i=0,j=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')j=-1;ch=getchar();}
    while(ch<='9'&&ch>='0'){i=i*10+ch-'0';ch=getchar();}
    return i*j;
}
void build(int k,int l,int r){
    if(l==r){
        mn[k]=sum[k]=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    sum[k]=sum[k<<1]+sum[k<<1|1];
    mn[k]=min(mn[k<<1],mn[k<<1|1]);
}
void modify(int k,int l,int r,int opx,int opv){
    if(l==r){
        mn[k]=sum[k]=opv;
        return;
    }
    int mid=(l+r)>>1;
    if(opx<=mid)modify(k<<1,l,mid,opx,opv);
    else modify(k<<1|1,mid+1,r,opx,opv);
    mn[k]=min(mn[k<<1],mn[k<<1|1]);
    sum[k]=sum[k<<1]+sum[k<<1|1];
}
long long querymn(int k,int l,int r,int opl,int opr){
    if(l>=opl&&r<=opr){return mn[k];}
    int mid=(l+r)>>1;
    long long res=1000000000000;
    if(opl<=mid)res=min(res,querymn(k<<1,l,mid,opl,opr));
    if(opr>mid)res=min(res,querymn(k<<1|1,mid+1,r,opl,opr));
    return res;
}
long long querysum(int k,int l,int r,int opl,int opr){
    if(l>=opl&&r<=opr){return sum[k];}
    int mid=(l+r)>>1;
    long long res=0;
    if(opl<=mid)res+=querysum(k<<1,l,mid,opl,opr);
    if(opr>mid)res+=querysum(k<<1|1,mid+1,r,opl,opr);
    return res;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)a[i]=qread();
    build(1,1,n);
    int op,l,r,v;
    for(int i=1;i<=m;i++){
        scanf("%d",&op);
        if(op==1){
            scanf("%d%d%d",&l,&r,&v);l++;r++;
            for(int j=l;j<=r;j++){
                a[j]=a[j]+v;
                modify(1,1,n,j,a[j]);
            }
        }
        if(op==2){
            scanf("%d%d%d",&l,&r,&v);l++;r++;
            for(int j=l;j<=r;j++){
                a[j]=floor((double)a[j]/(double)v);
                modify(1,1,n,j,a[j]);
            }
        }
        if(op==3){
            scanf("%d%d",&l,&r);l++;r++;
            printf("%lld\n",querymn(1,1,n,l,r));
        }
        if(op==4){
            scanf("%d%d",&l,&r);l++;r++;
            printf("%lld\n",querysum(1,1,n,l,r));
        }
    }
    return 0;
}
30分 暴力线段树(单点修改+区间查询)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 100010
#define INF 1000000000
using namespace std;
long long sum[maxn*4],maxs[maxn*4],mins[maxn*4],lazy[maxn*4];
int num[maxn*4];
void pushup(int k){
    sum[k]=sum[k<<1]+sum[k<<1|1];
    mins[k]=min(mins[k<<1],mins[k<<1|1]);
    maxs[k]=max(maxs[k<<1],maxs[k<<1|1]);
}
void pushlazy(int k,int lz,int len){
    mins[k]+=lz;
    maxs[k]+=lz;
    sum[k]+=lz*len;
    lazy[k]+=lz;
}
void pushdown(int l,int r,int k){
    if(lazy[k]!=0){
        int mid=(l+r)>>1;
        pushlazy(k<<1,lazy[k],mid-l+1);
        pushlazy(k<<1|1,lazy[k],r-mid);
        lazy[k]=0;
    }
    return;
}
void build(int l,int r,int k){
    if(l==r){
        sum[k]=mins[k]=maxs[k]=num[l];
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,k<<1);build(mid+1,r,k<<1|1);
    pushup(k);
}
void modify(int v,int l,int r,int opl,int opr,int k){
    if(l>=opl&&r<=opr){
        lazy[k]+=v;
        sum[k]+=v*(r-l+1);
        mins[k]+=v;
        maxs[k]+=v;
        return;
    }
    pushdown(l,r,k);
    int mid=(l+r)>>1;
    if(opl<=mid)modify(v,l,mid,opl,opr,k<<1);
    if(opr>mid)modify(v,mid+1,r,opl,opr,k<<1|1);
    pushup(k);
}
void div(int v,int l,int r,int opl,int opr,int k){
    if(l>=opl&&r<=opr){
        long long A,B;
        if(mins[k]<0)A=(mins[k]-v+1)/v;
        else A=mins[k]/v;
        if(maxs[k]<0)B=(maxs[k]-v+1)/v;
        else B=maxs[k]/v;
        if(A-mins[k]==B-maxs[k]){
            pushlazy(k,A-mins[k],r-l+1);
            return;
        }
    }
    pushdown(l,r,k);
    int mid=(l+r)>>1;
    if(opl<=mid)div(v,l,mid,opl,opr,k<<1);
    if(opr>mid)div(v,mid+1,r,opl,opr,k<<1|1);
    pushup(k);
}
long long querysum(int opl,int opr,int l,int r,int k){
    if(l>=opl&&r<=opr)return sum[k];
    pushdown(l,r,k);
    int mid=(l+r)>>1;
    long long ans=0;
    if(opl<=mid)ans+=querysum(opl,opr,l,mid,k<<1);
    if(opr>mid)ans+=querysum(opl,opr,mid+1,r,k<<1|1);
    return ans;
}
long long querymn(int opl,int opr,int l,int r,int k){
    if(l>=opl&&r<=opr)return mins[k];
    pushdown(l,r,k);
    int mid=(l+r)>>1;
    long long ans=INF;
    if(opl<=mid)ans=min(ans,querymn(opl,opr,l,mid,k<<1));
    if(opr>mid)ans=min(ans,querymn(opl,opr,mid+1,r,k<<1|1));
    return ans;
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&num[i]);
    build(1,n,1);
    int op,l,r,v;
    for(int i=1;i<=m;i++){
        scanf("%d",&op);
        if(op==1){
            scanf("%d%d%d",&l,&r,&v);
            modify(v,1,n,l+1,r+1,1);
        }
        if(op==2){
            scanf("%d%d%d",&l,&r,&v);
            div(v,1,n,l+1,r+1,1);
        }
        if(op==3){
            scanf("%d%d",&l,&r);
            printf("%lld\n",querymn(l+1,r+1,1,n,1));
        }
        if(op==4){
            scanf("%d%d",&l,&r);
            printf("%lld\n",querysum(l+1,r+1,1,n,1));
        }
    }
    return 0;
}
100分 区间修改+单点查询

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

Linux安装redis服务器和部署

Linux安装redis和部署 第一步:下载安装包 wget http://download.redis.io/releases/redis-5.0.5.tar.gz 访问https://redis.io/download 到官网进行下载。这里下载最新的5.0.5版本. 第二步:...

osc_3ytpwpyb
12分钟前
0
0
IF函数,根据条件设定输入内容

if函数通常用于条件判断,根据判断结果执行相应命令。 1.函数解释: IF(logical_test, [value_if_true], [value_if_false]) logical_test 必需。 计算结果为 TRUE 或 FALSE 的任何值或表达式...

osc_sumf8h95
14分钟前
0
0
Pytorch自定义dataloader以及在迭代过程中返回image的name

pytorch官方给的加载数据的方式是已经定义好的dataset以及loader,如何加载自己本地的图片以及label? 形如数据格式为 image1 label1 image2 label2 ... imagen labeln 实验中我采用的数据的...

osc_l8u38961
15分钟前
0
0
灯塔

\[love\ and \ share \] 我怎么感觉变成了好东西推荐呢?算了,本来也差不多 还没写完,想到再更 有好看玩的能不能评论一下,qwq 动漫 大多是些国漫,多在\(b\)站、腾讯视频、盗版小网站能够...

osc_dc6pbw3x
16分钟前
0
0
网易首页 」 网易手机 」 正文 苹果超薄触摸显示技术专利曝光:重新定义轻薄

最近,苹果公司的新屏幕专利技术已经曝光。特别是苹果公司的新型超薄触摸技术,它可以降低显示器的结构水平,消除多余的电路,并使屏幕更薄。该专利表明,这项新技术适用于iPhone,iPad,App...

osc_opzpp18v
18分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部