CF52C求助
查看原帖
CF52C求助
809165
The_Wandering_Earth楼主2023/1/25 21:26

rt,在学术版是因为这道题没几个人做,经过我的调试,发现样例中第二次修改之后,整个区间的min值还是1,理论上应该是0。

#include<bits/stdc++.h>
#define lid (id<<1)
#define rid (id<<1|1)
#define int long long     
using namespace std;
const int maxn=200005;
int n,q,m,ans,a[maxn];
struct seg_tree{
	int l,r,mn,add;
}tr[maxn<<2];
void build(int id,int l,int r){
	tr[id].l=l,tr[id].r=r;
	if(l==r){
		tr[id].mn=a[l];
		return;
	}
	int mid=(l+r)>>1;
	build(lid,l,mid);
	build(rid,mid+1,r);
	tr[id].mn=min(tr[lid].mn,tr[rid].mn);
}
void pushdown(int id){
	tr[lid].add+=tr[id].add,tr[rid].add+=tr[id].add;
	tr[lid].mn+=tr[id].add,tr[rid].mn+=tr[id].add;
	tr[id].add=0; 
	//cout<<id<<" "<<tr[id].l<<" "<<tr[id].r<<" "<<tr[id].mn<<" "<<tr[id].add<<endl;
}            
void change(int id,int l,int r,int k){
	if(tr[id].l==l&&tr[id].r==r){
		tr[id].add+=k,tr[id].mn+=k;
		return;     
	}
	pushdown(id);
	int mid=(tr[id].l+tr[id].r)>>1;
	if(r<=mid)change(lid,l,r,k);
	else if(l>mid)change(rid,l,r,k);
	else change(lid,l,mid,k),change(rid,mid+1,r,k);
	tr[id].mn=min(tr[lid].mn,tr[rid].mn);
}
int query(int id,int l,int r){
	if(tr[id].l==l&&tr[id].r==r)return tr[id].mn;
	pushdown(id);
	int mid=(tr[id].l+tr[id].r)>>1;
	if(r<=mid)return query(lid,l,r);
	else if(l>mid)return query(rid,l,r);
	else return min(query(lid,l,mid),query(rid,mid+1,r));
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	build(1,1,n);
	cin>>q;
	while(q--){
		int x,y,z;
		char c;
		cin>>x>>y;
		x++,y++;
		c=getchar();
		if(c!='\n'){
			cin>>z;
			z++;
			if(x>y)change(1,x,n,z),change(1,1,y,z);
			else change(1,x,y,z);
		}else{
			ans=1111111;
			if(x>y)ans=min(ans,min(query(1,x,n),query(1,1,y)));
			else ans=min(ans,query(1,x,y));
			cout<<ans<<endl;
		}
	}
	return 0;
}
2023/1/25 21:26
加载中...