线段树板子求助,玄关
  • 板块灌水区
  • 楼主ChenZQ
  • 当前回复11
  • 已保存回复11
  • 发布时间2024/3/20 22:25
  • 上次更新2024/3/21 13:33:27
查看原帖
线段树板子求助,玄关
745358
ChenZQ楼主2024/3/20 22:25

我做了好久,结果只有55/100,剩下的分全TLE了不知道为什么

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 400010;
int seg[N],tag[N],a[100010];
int n;

void pushdown(int u)
{
	seg[u*2]+=tag[u];seg[u*2+1]+=tag[u];
	tag[u*2]+=tag[u];tag[u*2+1]+=tag[u];
	tag[u]=0;
}
void build_tree(int l,int r,int u)
{
	if(l==r) 
	{
		seg[u]=a[l];
		return;
	}
	int mid=(l+r)>>1;
	build_tree(l,mid,u*2);build_tree(mid+1,r,u*2+1);
	seg[u]=min(seg[u*2],seg[u*2+1]);
}
string s;
int aa,b,c;
int ask(int l,int r,int u)
{
	if(l>=aa && r<=b) return seg[u];
    if(l>r) return 1414124241424;
    if(l==r) return 114514191914;
	int mid=(l+r)>>1;
	int mi=114514191414;
	pushdown(u);
	if(mid>=aa && l<=b) mi=min(mi,ask(l,mid,u*2));
	if(r>=aa && mid+1<=b) mi=min(mi,ask(mid+1,r,u*2+1));
	return mi; 
}
void add(int l,int r,int u)
{
	//cout<<l<<" "<<r<<endl;
	if(l>r) return;
	
	if(l>=aa && r<=b)
	{
		seg[u]+=c;
		tag[u]+=c;
		return;
	}
	if(l==r) return;
	pushdown(u);
	int mid=(l+r)/2;
	add(l,mid,u*2);
	add(mid+1,r,u*2+1);
	seg[u]=min(seg[u*2],seg[u*2+1]);
	return;
}
signed main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	build_tree(1,n,1);
	int m;
	scanf("%lld",&m);getline(cin,s);
	while(m--)
	{
		getline(cin,s);
		int t=s.length();
		int j=0;aa=b=c=0;
		int flag=0;
		while(j<t && s[j]>='0' && s[j]<='9') aa=aa*10+s[j]-'0',j++;
		j++;
		while(j<t && s[j]>='0' && s[j]<='9') b=b*10+s[j]-'0',j++;
		j++;
		if(j<s.length()) flag=1;
		//cout<<"j"<<j<<endl;
		while(j<t && ((s[j]>='0' && s[j]<='9' ) || s[j]=='-'))
		{
			if(s[j]=='-') flag=-1;
			else c=c*10+s[j]-'0';
			j++;
			//cout<<"c:"<<c<<endl;
		}
		c=c*flag;
		aa++,b++;
		//cout<<flag<<endl;
		//cout<<"input"<<aa<<" "<<b<<" "<<c<<endl;
		if(flag!=0) add(1,n,1);
		else printf("%lld\n",ask(1,n,1));
	}
}
2024/3/20 22:25
加载中...