把小煜

UID: 600, 注册于 2024-11-2 19:23:08, 最后登录于 2025-10-28 21:13:36, 最后活动于 2025-10-29 22:17:23.

解决了 197 道题目，RP: 222.62 (No. 10)

个人简介

我练习打字两年半，至今仍是一指禅。

一些模板

#include<bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
const int N=100010;
int n,m;
int idx;
struct node
{
	int fath,dep,dfn,siz;
	int top,son;
	vector<int>G;
}point[N];
void dfs1(int u,int fa)
{
	point[u].fath=fa; point[u].dep=point[fa].dep+1; point[u].siz=1;
	for(int v : point[u].G)
	{
		if(v==fa) continue;
		dfs1(v,u);
		point[u].siz+=point[v].siz;
		if(point[v].siz>point[point[u].son].siz) point[u].son=v;
	}
}
void dfs2(int u,int fatop)
{
	point[u].top=fatop; point[u].dfn=++idx;
	if(point[u].son) dfs2(point[u].son,fatop);
	for(int v:point[u].G) if(v!=point[u].son && v!=point[u].fath) 
		dfs2(v,v);
}
int a[N],val[N];
struct nodex
{
	int l,r,data,sum,lazy;
}t[N<<2];
void build(int p,int l,int r)
{
	t[p].l=l,t[p].r=r;
	t[p].lazy=0;
	if(l==r)
	{
		t[p].data=val[l];
		t[p].sum=val[l];
		return;
	}
	int mid=l+r>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	t[p].data=max(t[p<<1].data,t[p<<1|1].data);
	t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
}
void pushdown(int p)
{
	if(t[p].lazy)
	{
		t[p<<1].sum=t[p<<1].sum+t[p].lazy*(t[p<<1].r-t[p<<1].l+1);
		t[p<<1].data=t[p<<1].data+t[p].lazy;
		t[p<<1].lazy=t[p<<1].lazy+t[p].lazy;
		t[p<<1|1].sum=t[p<<1|1].sum+t[p].lazy*(t[p<<1|1].r-t[p<<1|1].l+1);
		t[p<<1|1].data=t[p<<1|1].data+t[p].lazy;
		t[p<<1|1].lazy=t[p<<1|1].lazy+t[p].lazy;
		t[p].lazy=0;
	}
}
void add1(int p,int x,int k)//单点修改
{
	if(t[p].l==t[p].r)
	{
		t[p].data+=k;
		t[p].sum+=k;
		return;
	}
	pushdown(p);
	int mid=t[p].l+t[p].r>>1;
	if(x<=mid) add1(p<<1,x,k);
	if(x>mid) add1(p<<1|1,x,k);
	t[p].data=max(t[p<<1].data,t[p<<1|1].data);
	t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
}
void add2(int p,int l,int r,int k)//区间修改
{
	if(l<=t[p].l && t[p].r<=r)
	{
		t[p].sum=t[p].sum+k*(t[p].r-t[p].l+1);
		t[p].data=t[p].data+k;
		t[p].lazy=t[p].lazy+k;
		return;
	}
	pushdown(p);
	int mid=t[p].l+t[p].r>>1;
	if(l<=mid) add2(p<<1,l,r,k);
	if(r>mid) add2(p<<1|1,l,r,k);
	t[p].data=max(t[p<<1].data,t[p<<1|1].data);
	t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
}
int querymax(int p,int l,int r)//区间查询最大值
{
	if(l<=t[p].l&&t[p].r<=r) return t[p].data;
	pushdown(p);
	int mid=t[p].l+t[p].r>>1;
	int ret=-inf;
	if(l<=mid) ret=max(ret,querymax(p<<1,l,r));
	if(r>mid) ret=max(ret,querymax(p<<1|1,l,r));
	return ret;
}
int querysum(int p,int l,int r)//区间求和查询
{
	if(l<=t[p].l && t[p].r<=r) return t[p].sum;
	pushdown(p);
	int mid=t[p].l+t[p].r>>1;
	int ret=0;
	if(l<=mid) ret+=querysum(p<<1,l,r);
	if(r>mid) ret+=querysum(p<<1|1,l,r);
	return ret;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<n;i++)
	{
		int u,v; cin>>u>>v;
		point[u].G.push_back(v);
		point[v].G.push_back(u);	
	}
	dfs1(1,0); dfs2(1,1);
	for(int i=1;i<=n;i++) val[point[i].dfn]=a[i];
	build(1,1,n);
	while(m--)
	{
		int op; cin>>op;
		if(op==1)//单点修改
		{
			int u,t; cin>>u>>t;
			add1(1,point[u].dfn,t);
			a[u]+=t;
		}
		if(op==2)//子树修改
		{
			int u,t; cin>>u>>t;
			add2(1,point[u].dfn,point[u].dfn+point[u].siz-1,t);
		}
		if(op==3)//路径修改
		{
			int u,v,t; cin>>u>>v>>t;
			while(point[u].top!=point[v].top)
			{
				if(point[point[u].top].dep>point[point[v].top].dep) 
					swap(u,v);
				add2(1,point[point[v].top].dfn,point[v].dfn,t);
				v=point[point[v].top].fath;
			}
			if(point[u].dep>point[v].dep) swap(u,v);
			add2(1,point[u].dfn,point[v].dfn,t);
		}
		if(op==4)//路径最大值查询 
		{
			int u,v; cin>>u>>v;
			int ans=-inf;
			while(point[u].top!=point[v].top)
			{
				if(point[point[u].top].dep>point[point[v].top].dep) 
					swap(u,v);
				ans=max(ans,querymax(1,point[point[v].top].dfn,point[v].dfn));
				v=point[point[v].top].fath;
			}
			if(point[u].dep>point[v].dep) swap(u,v);
			ans=max(ans,querymax(1,point[u].dfn,point[v].dfn));
			cout<<ans<<"\n";
		}
		if(op==5)//路径和查询 
		{
			int u,v; cin>>u>>v;
			int ans=0;
			while(point[u].top!=point[v].top)
			{
				if(point[point[u].top].dep>point[point[v].top].dep) 
					swap(u,v);
				ans+=querysum(1,point[point[v].top].dfn,point[v].dfn);
				v=point[point[v].top].fath;
			}
			if(point[u].dep>point[v].dep) swap(u,v);
			ans+=querysum(1,point[u].dfn,point[v].dfn);
			cout<<ans<<"\n";
		}
		if(op==6)//子树最大值查询
		{
			int u; cin>>u;
			int ans=querymax(1,point[u].dfn,point[u].dfn+point[u].siz-1);
			cout<<ans<<"\n";
		}
		if(op==7)//子树和查询
		{
			int u; cin>>u;
			int ans=querysum(1,point[u].dfn,point[u].dfn+point[u].siz-1);
			cout<<ans<<"\n";
		}
	}
	return 0; 
}

#include <bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
const int N=1e5+5;
int a[N],n,m;
struct node
{
	int l,r,data,sum,lazy;
}t[N<<2];
//建树 
void build(int p,int l,int r)
{
	t[p].l=l,t[p].r=r;
	t[p].lazy=0;
	if(l==r)
	{
		t[p].data=a[l];
		t[p].sum=a[l];
		return;
	}
	int mid=l+r>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	t[p].data=max(t[p<<1].data,t[p<<1|1].data);
	t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
}
// 传懒标记
void pushdown(int p)
{
	if(t[p].lazy)
	{
		//更新左子树
		t[p<<1].sum+=t[p].lazy*(t[p<<1].r-t[p<<1].l+1);
		t[p<<1].data+=t[p].lazy;
		t[p<<1].lazy+=t[p].lazy;
		//更新右子树
		t[p<<1|1].sum+=t[p].lazy*(t[p<<1|1].r-t[p<<1|1].l+1);
		t[p<<1|1].data+=t[p].lazy;
		t[p<<1|1].lazy+=t[p].lazy;
		t[p].lazy=0;
	}
}
// 单点修改
void add1(int p,int x,int k)
{
	if(t[p].l==t[p].r)
	{
		t[p].data+=k;
		t[p].sum+=k;
		return;
	}
	pushdown(p);
	int mid=t[p].l+t[p].r>>1;
	if(x<=mid) add1(p<<1,x,k);
	else add1(p<<1|1,x,k);
	t[p].data=max(t[p<<1].data,t[p<<1|1].data);
	t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
}
//区间查询最大值
int query1(int p,int l,int r)
{
	if(l<=t[p].l&&t[p].r<=r) return t[p].data;
	pushdown(p);
	int mid=t[p].l+t[p].r>>1;
	int ret=-inf;
	if(l<=mid) ret=max(ret,query1(p<<1,l,r));
	if(r>mid) ret=max(ret,query1(p<<1|1,l,r));
	return ret;
}
//区间修改
void add2(int p,int l,int r,int k)
{
	if(l<=t[p].l&&t[p].r<=r)
	{
		t[p].sum+=k*(t[p].r-t[p].l+1);
		t[p].data+=k;
		t[p].lazy+=k;
		return;
	}
	pushdown(p);
	int mid=t[p].l+t[p].r>>1;
	if(l<=mid) add2(p<<1,l,r,k);
	if(r>mid) add2(p<<1|1,l,r,k);
	t[p].data=max(t[p<<1].data,t[p<<1|1].data);
	t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
}
//区间求和查询
int query2(int p,int l,int r)
{
	if(l<=t[p].l&&t[p].r<=r) return t[p].sum;
	pushdown(p);
	int mid=t[p].l+t[p].r>>1;
	int ret=0;
	if(l<=mid) ret+=query2(p<<1,l,r);
	if(r>mid) ret+=query2(p<<1|1,l,r);
	return ret;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	build(1,1,n);
	for(int i=1;i<=m;i++)
	{
		int op;
		cin>>op;
		if(op==1)//单点修改
		{
			int x,k;
			cin>>x>>k;
			add1(1,x,k);
		}
		else if(op==2)//区间查询最大值
		{
			int l,r;
			cin>>l>>r;
			cout<<query1(1,l,r)<<"\n";
		}
		else if(op==3)//区间修改
		{
			int l,r,k;
			cin>>l>>r>>k;
			add2(1,l,r,k);
		}
		else if(op==4)//区间求和查询
		{
			int l,r;
			cin>>l>>r;
			cout<<query2(1,l,r)<<"\n";
		}
	}
	return 0;
}

惊喜

通过的题目
A0061

P1

edu001

G0037

A0096

A0001

A0002

A0003

A0004

A0005

A0006

A0007

A0008

A0009

A0010

A0011

A0012

A0013

A0014

A0015

A0016

A0017

A0018

A0019

A0020

A0021

A0022

A0023

A0024

A0025

A0026

A0053

A0027

A0028

A0029

A0030

A0031

A0032

A0033

A0034

A0035

A0036
A0038

A0039

A0040

A0041

A0042

A0043

A0044

A0045

A0046

A0047

A0049

A0050

A0051

A0052

CSPJ2020T1

CSPJ2020T2

CSPJ2022T1

A0054

A0055

A0056

A0057

A0058

A0059

A0060

A0062

A0063

A0064

A0065

A0066

A0067

NOIPS2012A

NOIP2011J2

A0068

A0069

A0070

A0071

A0072

NOIP2008

A0074

A0075

A0076

NOIPS2011T4
A0077

A0078

A0079

A0080

A0081

edu003

A0082

NOIPJ1999A

NOIPJ2008A

188

CSPJ2021A

CSPS2019A

CSPJ2023A

NOIPJ2002D

NOIP2005A

201

P1056

edu004

edu006

edu007

edu008

edu009

edu010

edu011

G0014

edu012

edu013

edu015

CSPJ2024T1

A0085

A0086

NOIP2015A

NOIPJ2014A

NOIPJ2018A

A0087

G0036

A0090

A0091

A0092

A0093

A0095

A0097
A0098

A0099

A0101

A0104

edu2001

edu3008

edu2002

edu2003

edu2004

edu2007

edu2008

edu2009

edu2010

edu2011

edu2012

edu2005

edu2006

edu2020

edu2023

edu2025

edu2026

edu2028

edu2029

edu2030

edu2050

edu2051

G0106

edu2031

edu2060

G0104

G0103

G0110

G0109

G0117

G0116

G0115

edu2013

edu2014

edu2015

edu2016
最近活动

教程: 19
stl: 7
高精度: 5
搜索: 5
枚举: 5
其他: 5
CSP-J: 4
模拟: 3
NOIP: 3
语法: 3
动态规划: 3
贪心: 3
构造: 3
2015: 2
2020: 2
NOIP 普及组: 2
NOIP 提高组: 2
A: 2
1: 1
2002: 1

把小煜

个人简介

我练习打字两年半，至今仍是一指禅。

我练习打字两年半，至今仍是一指禅。

我练习打字两年半，至今仍是一指禅。

我练习打字两年半，至今仍是一指禅。

我练习打字两年半，至今仍是一指禅。

我练习打字两年半，至今仍是一指禅。

一些模板

通过的题目

最近活动

题目标签

状态

开发

支持

把小煜

个人简介

我练习打字两年半，至今仍是一指禅。

我练习打字两年半，至今仍是一指禅。

我练习打字两年半，至今仍是一指禅。

我练习打字两年半，至今仍是一指禅。

我练习打字两年半，至今仍是一指禅。

我练习打字两年半，至今仍是一指禅。

一些模板

通过的题目

最近活动

题目标签

状态

开发

支持

还没有账户？

登录