2018.07.23[PA2015]Siano(线段树)
2024-10-20 16:34:33
[PA2015]Siano
描述
Description
农夫Byteasar买了一片n亩的土地,他要在这上面种草。 他在每一亩土地上都种植了一种独一无二的草,其中,第i亩土地的草每天会长高a[i]厘米。 Byteasar一共会进行m次收割,其中第i次收割在第d[i]天,并把所有高度大于等于b[i]的部分全部割去。Byteasar想知道,每次收割得到的草的高度总和是多少,你能帮帮他吗?
输入
Input
第一行包含两个正整数n,m(1<=n,m<=500000),分别表示亩数和收割次数。 第二行包含n个正整数,其中第i个数为ai,依次表示每亩种植的草的生长能力。 接下来m行,每行包含两个正整数d[i],bi,依次描述每次收割。 数据保证d[1]
输出
Output
输出m行,每行一个整数,依次回答每次收割能得到的草的高度总和。
样例输入
4 4
1 2 4 3
1 1
2 2
3 0
4 4
样例输出
6
6
18
0
提示
第1天,草的高度分别为1,2,4,3,收割后变为1,1,1,1。
第2天,草的高度分别为2,3,5,4,收割后变为2,2,2,2。
第3天,草的高度分别为3,4,6,5,收割后变为0,0,0,0。
第4天,草的高度分别为1,2,4,3,收割后变为1,2,4,3。
Source
By Claris
标签
BZOJ4293
不难发现如果将a[i]" role="presentation" style="position: relative;">a[i]a[i]排序,每次割完草后剩下的草的高度仍然是单调不减的。这样的话,我们维护线段树区间覆盖,区间加,区间和,维护查询区间内刚好小于等于某个数的下标。这样的话将割草拆成区间加之后查询区间内刚好小于等于某个数的下标,然后再讲大于割草高度的全部区间覆盖成割草高度,然后比较覆盖前后的区间和就行了。
代码如下:
#include<bits/stdc++.h>
#define ll long long
#define N 500005
#define lc (p<<1)
#define rc (p<<1|1)
#define mid (T[p].l+T[p].r>>1)
using namespace std;
inline ll read(){
ll ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
int n,m;
ll d1,a[N],sum[N];
struct Node{int l,r;ll maxn,sum,lz,bz;}T[N<<2];
inline ll max(ll a,ll b){return a>b?a:b;}
inline void pushup(int p){T[p].maxn=max(T[lc].maxn,T[rc].maxn),T[p].sum=T[lc].sum+T[rc].sum;}
inline void pushnow(int p,ll v){T[p].sum+=v*(sum[T[p].r]-sum[T[p].l-1]),T[p].maxn+=v*a[T[p].r],T[p].lz+=v;}
inline void pushnown(int p,ll v){T[p].bz=v,T[p].lz=0,T[p].sum=(T[p].r-T[p].l+1)*v,T[p].maxn=v;}
inline void pushdown(int p){
if(T[p].bz!=-1)pushnown(lc,T[p].bz),pushnown(rc,T[p].bz),T[p].bz=-1;
if(T[p].lz)pushnow(lc,T[p].lz),pushnow(rc,T[p].lz),T[p].lz=0;
}
inline void build(int p,int l,int r){
T[p].l=l,T[p].r=r,T[p].lz=0,T[p].bz=-1;
if(l==r){T[p].sum=T[p].maxn=0;return;}
build(lc,l,mid),build(rc,mid+1,r);
}
inline void modify(int p,int ql,int qr,ll v){
if(ql>T[p].r||qr<T[p].l)return;
if(ql<=T[p].l&&T[p].r<=qr){pushnown(p,v);return;}
pushdown(p);
if(qr<=mid)modify(lc,ql,qr,v);
else if(ql>mid)modify(rc,ql,qr,v);
else modify(lc,ql,mid,v),modify(rc,mid+1,qr,v);
pushup(p);
}
inline ll query(int p,ll v){
if(T[p].l==T[p].r)return T[p].l;
pushdown(p);
if(T[lc].maxn<=v)return query(rc,v);
return query(lc,v);
}
int main(){
n=read(),m=read();
for(int i=1;i<=n;++i)a[i]=read();
sort(a+1,a+n+1);
build(1,1,n);
for(int i=1;i<=n;++i)sum[i]=sum[i-1]+a[i];
d1=0;
while(m--){
ll d2=read(),b=read();
T[1].maxn+=(d2-d1)*a[n],T[1].sum+=(d2-d1)*sum[n],T[1].lz+=(d2-d1);
if(T[1].maxn<=b){puts("0"),d1=d2;continue;}
ll tmp=T[1].sum;
int pos=query(1,b);
modify(1,pos,n,b);
cout<<tmp-T[1].sum<<'\n',d1=d2;
}
return 0;
}
最新文章
- 【uoj58】 WC2013—糖果公园
- Java 解析XML的几种方法
- 40页PPT勾画“互联网颠覆性思维”----诠释互联网思维
- English Training Material - 05
- uva 10105
- 新手!SDK Manager里找不到API安装的选项怎么办?
- 洛谷1377 M国王 (SCOI2005互不侵犯King)
- java链接mysql添加中文和模糊查询
- [UWP]创建一个进度按钮
- Android预定义样式
- Java互联网应用和企业级应用的区别
- C语言中结构体(struct)的几种初始化方法
- 「SDOI2014」数数 解题报告
- 【python】——sql模拟
- converting the moment tensor to strie-dip-rake
- Android 发送邮件以及定时发送邮件的实现
- buildroot构建项目(七)--- u-boot 2017.11 适配开发板修改 4 ---- 系统启动初始化之四
- scrapy中Request中常用参数
- K-Means &; Sequential Leader Clustering
- ubuntu server静态IP和DNS服务器设置