DAY 8-9 线段树

训练地址：传送门

训练情况简介

早上：
下午：
晚上：

A 题

hdu 1166 敌兵布阵
题意：
单点修改，区间求和
思路：
今天使用线段树解决问题，之前的day3训练使用了树状数组解决问题

//>>>Qiansui
#include<map>
#include<set>
#include<list>
#include<stack>
#include<cmath>
#include<queue>
#include<deque>
#include<cstdio>
#include<string>
#include<vector>
#include<utility>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<functional>
#define ll long long
#define ull unsigned long long
#define mem(x,y) memset(x,y,sizeof(x))
#define debug(x) cout << #x << " = " << x << endl
#define debug2(x,y) cout << #x << " = " << x << " " << #y << " = "<< y << endl
//#define int long long

inline ll read()
{
	ll x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-48;ch=getchar();}
	return x*f;
}

using namespace std;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ull,ull> pull;
typedef pair<double,double> pdd;
/*
单点修改，区间查询
*/
const int maxm=5e4+5,inf=0x3f3f3f3f,mod=998244353;
int n,seg[4*maxm],a[maxm];
string ss;

void push_up(int p){
	seg[p]=seg[p*2]+seg[p*2+1];
	return ;
}

void build(int p,int pl,int pr){
	if(pl==pr){
		seg[p]=a[pl];
		a[pl]=p;
		return ;
	}
	int mid=(pl+pr)>>1;
	build(p*2,pl,mid);
	build(p*2+1,mid+1,pr);
	push_up(p);
	return ;
}

void update(int p,int x){//单点修改
	p=a[p];
	while(p){
		seg[p]+=x;
		p/=2;
	}
	return ;
}

int query(int l,int r,int p,int pl,int pr){//区间查询
	if(l<=pl&&r>=pr) return seg[p];
	int mid=(pl+pr)>>1,res=0;
	if(l<=mid) res+=query(l,r,p*2,pl,mid);
	if(r>mid) res+=query(l,r,p*2+1,mid+1,pr);
	return res;
}

void solve(){
	int c;
	cin>>c;
	for(int z=1;z<=c;++z){
		cout<<"Case "<<z<<":\n";
		cin>>n;
		for(int i=1;i<=n;++i){
			cin>>a[i];
		}
		build(1,1,n);
		int x,y,ans;
		while(cin>>ss){
			if(ss=="End") break;
			cin>>x>>y;
			if(ss=="Add"){
				update(x,y);
			}else if(ss=="Sub"){
				update(x,-y);
			}else{//"Query"
				ans=query(x,y,1,1,n);
				cout<<ans<<'\n';
			}
		}
	}
	return ;
}

signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int _=1;
//	cin>>_;
	while(_--){
		solve();
	}
	return 0;
}

B 题

hdu 1754 I Hate It
题意：
单点修改，区间查询最大值
思路：
线段树板子即可
记得关流或者快读，不然会TLE

//>>>Qiansui
#include<map>
#include<set>
#include<list>
#include<stack>
#include<cmath>
#include<queue>
#include<deque>
#include<cstdio>
#include<string>
#include<vector>
#include<utility>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<functional>
#define ll long long
#define ull unsigned long long
#define mem(x,y) memset(x,y,sizeof(x))
#define debug(x) cout << #x << " = " << x << endl
#define debug2(x,y) cout << #x << " = " << x << " " << #y << " = "<< y << endl
//#define int long long

inline ll read()
{
	ll x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-48;ch=getchar();}
	return x*f;
}

using namespace std;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ull,ull> pull;
typedef pair<double,double> pdd;
/*
单点修改，区间查询最大值
*/
const int maxm=2e5+5,inf=0x3f3f3f3f,mod=998244353;
int n,m,a[maxm],seg[maxm*4];

void push_up(int p){
	seg[p]=max(seg[p<<1],seg[(p<<1)+1]);
	return ;
}

void build(int p,int pl,int pr){
	if(pl==pr){
		seg[p]=a[pl];
		a[pl]=p;
		return ;
	}
	int mid=(pl+pr)>>1;
	build(p<<1,pl,mid);
	build((p<<1)+1,mid+1,pr);
	push_up(p);
	return ;
}

void update(int x,int y){
	x=a[x];
	seg[x]=y;
	x>>=1;
	while(x){
		push_up(x);
		x>>=1;
	}
	return ;
}

int query(int l,int r,int p,int pl,int pr){
	if(l<=pl&&pr<=r) return seg[p];
	int ans=0,mid=(pl+pr)>>1;
	if(l<=mid) ans=max(ans,query(l,r,p<<1,pl,mid));
	if(r>mid) ans=max(ans,query(l,r,(p<<1)+1,mid+1,pr));
	return ans;
}

void solve(){
	while(cin>>n){
		cin>>m;
		for(int i=1;i<=n;++i){
			cin>>a[i];
		}
		build(1,1,n);
		string ss;
		int x,y,ans;
		for(int i=0;i<m;++i){
			cin>>ss>>x>>y;
			if(ss=="Q"){
				ans=query(x,y,1,1,n);
				cout<<ans<<'\n';
			}else{//"U"
				update(x,y);
			}
		}
	}
	return ;
}

signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int _=1;
//	cin>>_;
	while(_--){
		solve();
	}
	return 0;
}

题

题意：

思路：