RE与MLE求助
查看原帖
RE与MLE求助
631713
Amano_Hina楼主2022/3/14 18:38

rt,我的代码是由树状数组1的代码改改提交上去的

Code(树状数组):

#include <bits/stdc++.h>
#define MAX 1000005
using namespace std;
long long int gcd(int a,int b)
{
     return b ? gcd(b,a%b) : a;
}
int a[MAX*4];
struct a
{
    int l,r,kind;
    bool ye;
} tree[MAX*4];
void build(int n,int l,int r)
{
    int mid=(l+r)/2;
    tree[n].l=l;tree[n].r=r;
    if(l==r)
    {
        tree[n].ye=true;
        tree[n].kind=a[l];
        return;
    }else{
        build(n*2,l,mid);
        build(n*2+1,mid+1,r);
        tree[n].kind=tree[n*2].kind+tree[n*2+1].kind;
    }
}
void add(int x,int k,int now)
{
    int mid=(tree[now].l+tree[now].r)/2;
    if(tree[now].l==tree[now].r)
    {
        tree[now].kind+=k;
        return;
    }else{
        if(x>mid) add(x,k,now*2+1);else
         add(x,k,now*2);
        tree[now].kind=tree[now*2].kind+tree[now*2+1].kind;
    }
}
long long int find(int l,int r,int n)
{
    int mid=(tree[n].l+tree[n].r)/2;
    if(tree[n].l==l&&tree[n].r==r)
    {
        return tree[n].kind;
    }
    if( l > mid ) return find( l , r , n * 2 + 1 ); 
    else if( mid >= r ) return find( l , r , n * 2 ); 
    return find( l , mid , n * 2 ) + find( mid + 1 , r , n * 2 + 1 ); 
}
int main()
{
    int n;
    cin>>n;
    int x;
    cin>>x;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    build(1,1,n);
    for(int i=1;i<=x;i++)
    {
        int a;
        cin>>a;
        if(a==1)
        {
            int x,k;
            cin>>x>>k;
            add(x,k,1);
        }else{
            int x,y;
            cin>>x>>y;
            cout<<find(x,y,1)<<endl;
        }
    }
    return 0;
}

Code(线段树)

#include <bits/stdc++.h>
#define MAX 1000005
using namespace std;
long long int gcd(int a,int b)
{
     return b ? gcd(b,a%b) : a;
}
int a[MAX*4];
struct a
{
    int l,r,kind;
    bool ye;
} tree[MAX*4];
void build(int n,int l,int r)
{
    int mid=(l+r)/2;
    tree[n].l=l;tree[n].r=r;
    if(l==r)
    {
        tree[n].ye=true;
        tree[n].kind=a[l];
        return;
    }else{
        build(n*2,l,mid);
        build(n*2+1,mid+1,r);
        tree[n].kind=tree[n*2].kind+tree[n*2+1].kind;
    }
}
void ac(int l,int r,int now,int k)
{
	/*int mid=(tree[now].l+tree[now].r)/2;
    if(tree[now].l==tree[now].r)
    {
        tree[now].kind+=k;
        return;
    }else{
        if(x>mid) add(x,k,now*2+1);else
         add(x,k,now*2);
        tree[now].kind=tree[now*2].kind+tree[now*2+1].kind;
    }*/

	if(tree[tree[now].l].ye==1&&tree[tree[now].r].ye==1)
	{
		tree[tree[now].l].kind+=k;
		tree[tree[now].r].kind+=k;
		tree[now].kind=tree[tree[now].l].kind+tree[tree[now].r].kind;
		return;
	}else{
		ac(l,tree[tree[now].l].r,tree[now].l,k);
		ac(tree[tree[now].r].l,r,tree[now].r,k);
		tree[now].kind=tree[tree[now].l].kind+tree[tree[now].r].kind;
	}
}
//	tree[now].kind+=k;

void add(int x,int y,int k,int now)
{
    int mid=(tree[now].l+tree[now].r)/2;
    if(tree[now].l==x&&tree[now].r==y)
    {
//        tree[now].kind+=k;
		ac(x,y,now,k);
        return;
    }else{
        if(x>mid) add(x,y,k,now*2+1);else
         add(x,y,k,now*2);
        tree[now].kind=tree[now*2].kind+tree[now*2+1].kind;
    }
}
long long int find(int l,int r,int n)
{
    int mid=(tree[n].l+tree[n].r)/2;
    if(tree[n].l==l&&tree[n].r==r)
    {
        return tree[n].kind;
    }
    if( l > mid ) return find( l , r , n * 2 + 1 ); 
    else if( mid >= r ) return find( l , r , n * 2 ); 
    return find( l , mid , n * 2 ) + find( mid + 1 , r , n * 2 + 1 ); 
}
int main()
{
    int n;
    cin>>n;
    int x;
    cin>>x;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    build(1,1,n);
    for(int i=1;i<=x;i++)
    {
        int a;
        cin>>a;
        if(a==1)
        {
            int x,y,k;
            cin>>x>>y>>k;
            add(x,y,k,1);
        }else{
            int x,y;
            cin>>x>>y;
            cout<<find(x,y,1)<<endl;
        }
    }
    return 0;
}
话说这两个有啥不同啊
2022/3/14 18:38
加载中...