AtCoder Beginner Contest 343:起航
2024/3/2/22:53
有点儿晚了,简单总结一下。
-
前4题都很基础,一点点小思维,其中C题 边界又盲目追求刚刚好,WA了一次,总结经验,程序实际设计应该略微大于数据范围。
-
EFG开始就做不动了,只剩了20多分钟,先通读然后看E题,E题读了半天发现大概是体积交并反推位置,不会。。。看F题,能不能分块呢?可以尝试一下。最后选择写线段树,只需要维护一下最大值次大值就行。
-
建议下次从C题开始做。
F
维护最大值和次大值,麻烦的地方全在 pushup
.简单来说有两点:
- 考虑被换掉的最大值能否更新次大值
- 考虑两个区间最大值相等的情况。次大值同理。
对此分讨即可。
注意 pushup
写成 node
类型,update
时的上传和query
时的合并写法略微不同,不要改了个返回值就反应不过来了。
#include<bits/stdc++.h>
#define F(i,l,r) for(int i=l;i<=r;++i)
#define G(i,r,l) for(int i=r;i>=l;--i)
using namespace std;
using ll = long long;
const int N=2e5+5;
struct node{
int sum,tot,mx,nx;
}tr[N<<2];
int n,q,a[N];
node pushup(node a,node b){
node c;
if(a.mx>b.mx){
c.sum=a.sum,c.mx=a.mx;
if(a.nx>b.mx) c.tot=a.tot,c.nx=a.nx;
else if(a.nx<b.mx) c.tot=b.sum,c.nx=b.mx;
else c.tot=a.tot+b.sum,c.nx=b.mx;
} else if(a.mx<b.mx){
c.sum=b.sum,c.mx=b.mx;
if(b.nx>a.mx) c.tot=b.tot,c.nx=b.nx;
else if(b.nx<a.mx) c.tot=a.sum,c.nx=a.mx;
else c.tot=b.tot+a.sum,c.nx=a.mx;
} else{
c.mx=a.mx,c.sum=a.sum+b.sum;
if(!a.nx && !b.nx) c.nx=c.tot=0;
else if(a.nx>b.nx) c.nx=a.nx,c.tot=a.tot;
else if(a.nx<b.nx) c.nx=b.nx,c.tot=b.tot;
else c.nx=a.nx,c.tot=a.tot+b.tot;
}
return c;
}
void update(int p,int l,int r,int x,int k){
if(l==r){
tr[p].mx=k;
tr[p].sum=1;
return ;
}
int mid=(l+r)>>1;
if(x<=mid) update(p*2,l,mid,x,k);
else update(p*2+1,mid+1,r,x,k);
tr[p]=pushup(tr[p*2],tr[p*2+1]);
}
node query(int p,int l,int r,int x,int y){
if(x<=l && r<=y) return tr[p];
int mid=(l+r)>>1;
node z=(node){0,0,0,0};
if(x<=mid) z=pushup(z,query(p*2,l,mid,x,y));
if(y>mid) z=pushup(z,query(p*2+1,mid+1,r,x,y));
return z;
}
signed main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin>>n>>q;
F(i,1,n<<2) tr[i]=(node){0,0,0,0};
F(i,1,n) {
cin>>a[i];
update(1,1,n,i,a[i]);
}
int op,x,y;
F(i,1,q){
cin>>op>>x>>y;
if(op==1){
update(1,1,n,x,y);
}
else {
node z=query(1,1,n,x,y);
cout<<z.tot<<'\n';
}
}
return 0;
}
标签:node,AtCoder,Beginner,int,tot,else,nx,343,mx
From: https://www.cnblogs.com/superl61/p/18049440