线段树求助
查看原帖
线段树求助
333800
qip101楼主2022/9/30 20:52
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define MAXN 100100 
using namespace std;
int n,m;
struct node{
	int L,R;//记录结点代表的区间的左右端点 
	long long w;//存储数据 
	long long tag;//标记值 
}tree[MAXN<<2];
inline void pushup(const int u)
{
	tree[u].w=tree[u*2].w+tree[u*2+1].w;
}
inline void build(const int u,int L,int R)
{
	if(L==R)
	{
		tree[u].w=0;
		return;
	}
	int M=(L+R)/2;
	build(u*2,L,M);
	build(u*2+1,M+1,R);
	pushup(u);
}
inline bool InRange(int L,int R,int l,int r)
{
	return (l<=R) && (L<=l);
}
inline bool OutofRange(int L,int R,int l,int r)
{
	return (L>r) || (R<l);
}
inline void pushdown(int u,int L,int R)
{
    tree[u*2].tag+=tree[u].tag;
    tree[u*2+1].tag+=tree[u].tag;
    tree[u*2].w+=tree[u].tag*(tree[u*2].R-tree[u*2].L+1);
    tree[u*2+1].w+=tree[u].tag*(tree[u*2+1].R-tree[u*2+1].L+1);
    tree[u].tag=0;
}
inline long long query(int u,int L,int R,int p)
{
	if(L==R)
		return tree[u].w;
	else
	{
		int M=(L+R)/2;
		pushdown(u,L,R);
		if(M>=p)
			return query(u*2,L,M,p);
		else
			return query(u*2+1,M+1,R,p);
	}
}
inline void update(int u,int L,int R,int l,int r)
{
	if(InRange(L,R,l,r))
	{
		tree[u].w+=(tree[u].R-tree[u].L+1);
		tree[u].tag++;
		return;
	}
	else if(!OutofRange(L,R,l,r))
	{
		int M=(L+R)/2;
		pushdown(u,L,R);
		update(u*2,L,M,l,r);
		update(u*2+1,M+1,R,l,r);
		pushup(u);
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n >> m;
	build(1,1,n);
	for(register int i=1;i<=m;i++)
	{
		int t;
		cin >> t;
		if(t==1)
		{
			int L,R;
			cin >> L >> R;
			update(1,1,n,L,R);
		}
		if(t==2)
		{
			int k;
			cin >> k;
			cout << query(1,1,n,k) << endl;
		}
	}
	return 0;
}
2022/9/30 20:52
加载中...