「vijos1083」小白逛公园
描述
小新经常陪小白去公园玩，也就是所谓的遛狗啦…在小新家附近有一条“公园路”，路的一边从南到北依次排着n个公园，小白早就看花了眼，自己也不清楚该去哪些公园玩了。
一开始，小白就根据公园的风景给每个公园打了分-.-。小新为了省事，每次遛狗的时候都会事先规定一个范围，小白只可以选择第a个和第b个公园之间（包括a、b两个公园）选择连续的一些公园玩。小白当然希望选出的公园的分数总和尽量高咯。同时，由于一些公园的景观会有所改变，所以，小白的打分也可能会有一些变化。
那么，就请你来帮小白选择公园吧。
输入格式
第一行，两个整数N和M，分别表示表示公园的数量和操作（遛狗或者改变打分）总数。
接下来N行，每行一个整数，依次给出小白 开始时对公园的打分。
接下来M行，每行三个整数。第一个整数K，1或2。K=1表示，小新要带小白出去玩，接下来的两个整数a和b给出了选择公园的范围（1≤a,b≤N， a可以大于b！）；K=2表示，小白改变了对某个公园的打分，接下来的两个整数p和s，表示小白对第p个公园的打分变成了s（1≤p≤N）。
其中，1≤N≤500 000，1≤M≤100 000，所有打分都是绝对值不超过1000的整数。
输出格式
小白每出去玩一次，都对应输出一行，只包含一个整数，表示小白可以选出的公园得分和的最大值。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
#include<iostream> #include<cstdio> using namespace std; struct data1{ int lm,rm,mx; int sum; int l,r; }tree[2000001]; int n,m; int a[500001]; void update(int k) { tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum; tree[k].lm=max(tree[k<<1].lm,tree[k<<1].sum+tree[k<<1|1].lm); tree[k].rm=max(tree[k<<1|1].rm,tree[k<<1].rm+tree[k<<1|1].sum); tree[k].mx=max(max(tree[k<<1].mx,tree[k<<1|1].mx),tree[k<<1].rm+tree[k<<1|1].lm); } void build(int k,int s,int t) { tree[k].l=s;tree[k].r=t; if(s==t){tree[k].sum=tree[k].lm=tree[k].rm=tree[k].mx=a[s];return;} int mid=(s+t)>>1; build(k<<1,s,mid); build(k<<1|1,mid+1,t); update(k); } data1 ask(int k,int p,int q) { data1 g,h,a; int l=tree[k].l,r=tree[k].r; if(l==p&&q==r)return tree[k]; int mid=(l+r)>>1; if(q<=mid) return ask(k<<1,p,q); else if(p>mid) return ask(k<<1|1,p,q); else{ g=ask(k<<1,p,mid); h=ask(k<<1|1,mid+1,q); a.mx=max(max(g.mx,h.mx),g.rm+h.lm); a.rm=max(h.sum+g.rm,h.rm); a.lm=max(g.lm,g.sum+h.lm); return a; } } void change(int k,int x,int y) { int l=tree[k].l,r=tree[k].r; if(l==r){tree[k].sum=tree[k].lm=tree[k].rm=tree[k].mx=y;return;} int mid=(l+r)>>1; if(x<=mid)change(k<<1,x,y); else if(x>mid)change(k<<1|1,x,y); update(k); } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); build(1,1,n); for(int i=1;i<=m;i++) { int t,x,y; scanf("%d%d%d",&t,&x,&y); if(t==1) { if(x>y)swap(x,y); printf("%d\n",ask(1,x,y).mx); } if(t==2) change(1,x,y); } return 0; } |
Subscribe
计数器 9787478
OI 课件=>
OI 课件=>