这题线段树动态开点都过不了吗
  • 板块P4939 Agent2
  • 楼主sjwhsss
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/8/13 20:24
  • 上次更新2024/8/13 22:42:13
查看原帖
这题线段树动态开点都过不了吗
982518
sjwhsss楼主2024/8/13 20:24

rt

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e7+5;
int n , q , a[maxn] , sum[maxn<<1] , tag[maxn<<1] , ls[maxn<<1] , rs[maxn<<1] , cnt=0;
inline ll input()
{
	char c=getchar();
	ll x=0,f=1;
	while(!isdigit(c)){if(c=='-')f*=-1;c=getchar();}
	while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}
inline void print(ll x)
{
	if(x<0)putchar('-'),x=-x;
	if(x>9)print(x/10);
	putchar(x%10+48);
}
void PushUp(int p)
{
	sum[p]=sum[ls[p]]+sum[rs[p]];
}
void PushDown(int p , int l , int r)
{
	if (!p)return;
	int mid = l + r >> 1;
	sum[ls[p]]+=tag[p]*(mid - l + 1);
	sum[rs[p]]+=tag[p]*(r - mid);
	tag[ls[p]]+=tag[p];
	tag[rs[p]]+=tag[p];
	tag[p]=0;
	return;
}
void Build(int &p , int l , int r)
{
	if (!p)p=++cnt;
	if (l == r){sum[p]=a[l];return;}
	int mid = l + r >> 1;
	Build(ls[p] , l , mid);
	Build(rs[p] , mid + 1 , r);
	PushUp(p);
	return;
}
void Add(int &p , int l , int r , int L , int R , ll val)
{
	if (!p)p=++cnt;
	if (L <= l && r <= R){sum[p]+=val,tag[p]+=val;return;};
	int mid = l + r >> 1;
	PushDown(p , l , r);
	if (L <= mid)Add(ls[p] , l , mid , L , R , val);
	if (R > mid)Add(rs[p] , mid + 1 , r , L , R , val);
	PushUp(p);
}
ll Query(int p , int l , int r , int L , int R)
{
	if (L <= l && r <= R)return sum[p];
	int mid = l + r >> 1;
	PushDown(p , l , r);
	ll res = 0;
	if (L <= mid)res += Query(ls[p] , l , mid , L , R);
	if (R > mid)res += Query(rs[p] , mid + 1 , r , L , R);
	return res;
}
int main ()
{
	n=input(),q=input();
	int rt=0;
	Build(rt , 1 , n);
	while(q--)
	{
		int op;
		op=input();
		if (!op)
		{
			int a=input(),b=input();
			Add(rt , 1 , n , a , b , 1);
		}
		else 
		{
			int a=input();
			print(Query(rt , 1 , n , a , a));
			putchar('\n');
		}
	}
	return 0;
}

2024/8/13 20:24
加载中...