蒟蒻求助WA
  • 板块CF52C Circular RMQ
  • 楼主Lips
  • 当前回复6
  • 已保存回复6
  • 发布时间2020/8/9 16:55
  • 上次更新2023/11/6 20:50:17
查看原帖
蒟蒻求助WA
342090
Lips楼主2020/8/9 16:55

WA#25,help!WA\#25,help!

#include<cstdio>
#include<algorithm>
using namespace std;
bool flag;
inline int lc(int p){return p<<1;}
inline int rc(int p){return p<<1|1;}
inline int read()
{
	int s=0,w=1;
	flag=0;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')s=s*10+(ch-'0'),ch=getchar();
	if(ch==' ') flag=1;
	return s*w;
}
const int MAXN=800010;
typedef long long ll;
int n,m;
ll a[MAXN],tag[MAXN],tree[MAXN],v;
inline void push_up(int u)
{
	tree[u]=min(tree[lc(u)],tree[rc(u)]);
}
inline void lazy_tag(int u,int l,int r,ll k)
{
	tag[u]+=k;
	tree[u]+=k;
}
inline void push_down(int u,int l,int r)
{
	int mid=(l+r)>>1;
	lazy_tag(lc(u),l,mid,tag[u]);
	lazy_tag(rc(u),mid+1,r,tag[u]);
	tag[u]=0;
}
void build(int u,int l,int r)
{
	if(l==r)
	{
		tree[u]=a[l];
		return;
	}
	int mid=(l+r)>>1;
	build(lc(u),l,mid);
	build(rc(u),mid+1,r);
	push_up(u);
} 
void update(int u,int l,int r,int ln,int rn,ll k)
{
	if(ln<=l&&r<=rn)
	{
		lazy_tag(u,l,r,k);
		return;
	}
	push_down(u,l,r);
	int mid=(l+r)>>1;
	if(ln<=mid) update(lc(u),l,mid,ln,rn,k);
	if(rn>mid) update(rc(u),mid+1,r,ln,rn,k);
	push_up(u);
} 
ll query(int u,int l,int r,int ln,int rn)
{
	ll t=1e9;
	if(ln<=l&&r<=rn) return min(t,tree[u]);
	push_down(u,l,r);
	int mid=(l+r)>>1;
	if(ln<=mid) t=min(t,query(lc(u),l,mid,ln,rn));
	if(rn>mid) t=min(t,query(rc(u),mid+1,r,ln,rn));
	return t;
}
void inc(int x,int y,ll w)
{
	if(x<=y) update(1,1,n,x,y,w);
	else update(1,1,n,x,n,w),update(1,1,n,1,y,w);
}
void rmq(int x,int y)
{
	if(x<=y) printf("%lld\n",query(1,1,n,x,y));
	else printf("%lld\n",min(query(1,1,n,x,n),query(1,1,n,1,y)));
}
int main()
{
	n=read();
	for(register int i=1;i<=n;i++) scanf("%lld",&a[i]);
	build(1,1,n);
	m=read();
	while(m--)
	{
		int x=read()+1,y=read()+1;
		if(flag) v=read(),inc(x,y,v);
		else rmq(x,y);
	}
	return 0;
	
}
2020/8/9 16:55
加载中...