首页 > 其他分享 >AtCoder Beginner Contest 343:起航

AtCoder Beginner Contest 343:起航

时间:2024-03-02 23:25:16浏览次数:34  
标签:node AtCoder Beginner int tot else nx 343 mx

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

相关文章

  • AtCoder Beginner Contest 343
    B-AdjacencyMatrix难度:⭐题目大意给定一个无向图的邻接矩阵,问每个节点都和哪些节点相练;解题思路没啥好说的;神秘代码#include<bits/stdc++.h>#defineintlonglong#defineIOSios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#defineendl'\n'......
  • AtCoder Beginner Contest 343(小白来了)
    A-WrongAnswer思路:给你两个数(A,B0~9)输出非A+B(0~9)解法:许多(A+B)^1等等Code:#include<iostream>usingnamespacestd;intmain(){intA,B;cin>>A>>B;cout<<!(A+B);return0;}B-AdjacencyMatrix思路......
  • AtCoder Beginner Contest 342
    B-Whichisahead?难度:⭐题目大意给定n个人的位置顺序,现有m次询问,给出a,b两个人,问谁在前面;解题思路模拟就行;神秘代码#include<bits/stdc++.h>#defineintlonglong#defineIOSios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#defineendl......
  • AtCoder DP Contest vp 记录
    题单。A从\(i-1\)与\(i-2\)转移即可。#include<bits/stdc++.h>usingnamespacestd;intn;inth[100031];intdp[100031];intmain(){ cin>>n; for(inti=1;i<=n;i++)cin>>h[i]; memset(dp,0x3f,sizeof(dp)); dp[1]=0; for(inti=1;i<......
  • p3435-solution
    P3435Solutionlink画个图:显然四个黄色部分是相等的。也就是说,黄色部分是A的一个border。根据题目,周期的长度也就是Q的长度,也就是A的长度减去它的某个border的长度。现在要求这个最大,由于A的长度固定,要求的也就是A的最小border长度。根据KMP求出来的nxt......
  • AtCoder Regular Contest 172
    Preface开学了小溜一下之前没打的ARC,结果这场后面没有计数改成数论了又给我创飞了这场的DE都太玄学了,属于是自己想半天一点屌思路没有然后看一眼题解就顿悟的类型总结就是菜得发昏A-Chocolate挺有意思的签到题考虑从大到小依次切,对于一个原来\(H'\timesW'\)的块,为了尽量......
  • AtCoder Beginner Contest 342
    AtCoderBeginnerContest342比赛链接开学了,以后codeforces大概率只能补题了,但是atcoder还是可以做的A-Yay!思路找出只出现一次的字符就可以Code#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongvoidsolve(){ strings; cin>>s; std::map<ch......
  • AtCoder Beginner Contest 342
    D.SquarePair给你一个数组,最多2e5个元素,每个元素的范围是0到2e5问选出两个元素,乘积为完全平方数的情况有多少?(任选a[i]a[j],且满足i<j)一种思路是用map记录数组的元素,选出一个元素x后,枚举所有完全平方数,如果完全平方数可以整除选出的这个元素且整除的结果y在map......
  • Toyota Programming Contest 2024#2(AtCoder Beginner Contest 341)D - Only one of two
    目录链接题面题意题解代码总结链接D-Onlyoneoftwo题面题意求第\(k\)个只能被\(N\)或\(M\)整除的数题解\([1,x]\)中的能被\(n\)整除的数有\(\lfloor\frac{x}{n}\rfloor\)个\([1,x]\)中的能被\(m\)整除的数有\(\lfloor\frac{x}{m}\rfloor\)个\([1,x]\)中的能被\(n\)......
  • HUAWEI Programming Contest 2024(AtCoder Beginner Contest 342)
    HUAWEIProgrammingContest2024(AtCoderBeginnerContest342)A-Yay!代码:#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;usingpii=pair<ll,ll>;#definefifirst#definesesecondusingi128=__int128_t;usingpiii=p......