求助
查看原帖
求助
366338
fjy666楼主2020/12/5 19:44

RT,为什么3个月前的代码能AC,而现在却TLE
AC代码

#include <cstring>
#include <cstdio>
#include <cctype>
#define REP(i,k,n) for(ll i=k;i<=n;++i)
#define ll long long
#define N 500010
using namespace std;
//快读和快写 
struct Node{ll l=0,r=0,sum=0;}tree[5*N];
ll inp[N],n,m,i;
ll flag,l,r;
inline ll read(void)
{
	ll x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();} 
	return x*f;
}
inline void write(ll x)
{
	if(x<0){putchar('-');x=-x;}
	if(x>9)write(x/10);
	putchar(x%10+'0');
	return;
}
void Built(ll i,ll l,ll r)
{
	tree[i].l=l;tree[i].r=r;
	if(l==r){tree[i].sum=inp[l];return;}
	ll mid=(l+r)>>1;
	Built(i<<1,l,mid);
	Built((i<<1)+1,mid+1,r);
	tree[i].sum=tree[i<<1].sum+tree[(i<<1)+1].sum;
}
ll Search(int i,int l,int r)
{
	if(tree[i].l>=l&&tree[i].r<=r)return tree[i].sum;
	if(tree[i].r<l||tree[i].l>r)return 0;
	ll sum=0;
	if(tree[i<<1].r>=l)sum+=Search(i<<1,l,r);
	if(tree[(i<<1)+1].l<=r)sum+=Search((i<<1)+1,l,r);
	return sum;
}
void Add(ll i,ll dis,ll k)
{
	if(tree[i].l==tree[i].r){tree[i].sum+=k;return;}
	if(dis<=tree[i<<1].r)Add(i<<1,dis,k);
	else Add((i<<1)+1,dis,k);
	tree[i].sum+=k;
	return;
}
int main()
{
	n=read();m=read();
	REP(i,1,n)
		inp[i]=read();
	Built(1,1,n);
	REP(i,1,m)
	{
		flag=read();
		l=read();
		r=read();
		switch(flag)
		{
			case 1:Add(1,l,r);break;
			case 2:write(Search(1,l,r));putchar('\n');break;
		}
	}
	return 0;
}

TLE代码

#include <cstdio>
#include <cctype>
using namespace std;
const int kMaxn=500000+1;
inline int read(void)
{
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();} 
	return x*f;
}
inline void write(int x)
{
	if(x<0){putchar('-');x=-x;}
	if(x>9)write(x/10);
	putchar(x%10+'0');
	return;
}
struct Segment_Tree
{
// 	private:
		struct{
			int l,r,sum;
		}t[4*kMaxn];
		inline int L(int ind){return ind<<1;}
		inline int R(int ind){return ind<<1|1;}
// 	public:
		void Build(int i,int l,int r,int* a)
		{
			t[i].l=l,t[i].r=r;
			if(l==r){t[i].sum=a[l];return;}
			int mid=(l+r)>>1;
			Build(L(i),l,mid,a);
			Build(R(i),mid+1,r,a);
			t[i].sum=t[L(i)].sum+t[R(i)].sum;
		}
		void Update(int i,int ind,int upd)
		{
			if(t[i].l==t[i].r)
			{
				t[i].sum+=upd;
				return;
			}
			if(t[L(i)].r>=ind)Update(L(i),ind,upd);
			else Update(R(i),ind,upd);
			t[i].sum=t[L(i)].sum+t[R(i)].sum;
		}
		int Query(int i,int l,int r)
		{
			if(t[i].l==t[i].r)return t[i].sum;
			int Ans=0;
			if(t[L(i)].r>=l)Ans+=Query(L(i),l,r);
			if(t[R(i)].l<=r)Ans+=Query(R(i),l,r);
			return Ans;
		}
}Tree; 
int a[kMaxn];
int main()
{
	int n,m;
	n=read(),m=read();
	for(int i=1;i<=n;++i)
        a[i]=read();
	Tree.Build(1,1,n,a);
	for(int i=1;i<=m;++i)
	{
		int op,x,y;
		op=read(),x=read(),y=read();
		if(op==1)Tree.Update(1,x,y);
		if(op==2)write(Tree.Query(1,x,y)),putchar('\n');
	}
	return 0;
}

数据有没有加强过?

2020/12/5 19:44
加载中...