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;
}
数据有没有加强过?