代码求调

大海中的孤帆 @ 2024-02-11 12:28:44

#include<bits/stdc++.h>
using namespace std;
struct k
{
    int l,r,ans;
}xds[400010];
int a[1000010];
int n,m;
void build(int ll,int rr,int kk)//set tree
{
    if(ll==rr)
    {
        xds[kk].ans=a[ll];
        return;
    }
    int mid=(ll+rr)>>1;
    build(ll,mid,kk*2);
    build(mid+1,rr,kk*2+1);
    xds[kk].l=ll;
    xds[kk].r=rr;
    xds[kk].ans=xds[kk*2].ans+xds[kk*2+1].ans;
    return;
}
int add(int ll,int rr,int kk)
{
    if(ll==xds[kk].l&&rr==xds[kk].r)
    {
        return xds[kk].ans;
    }
    if(ll==rr)
    {
        return xds[kk].ans;
    }
    int final=0;
    int mid=(xds[kk].l+xds[kk].r)>>1;
    if(ll<=mid)
    {
        final+=add(ll,mid,kk*2);
    }
    if(rr>mid)
    {
        final+=add(mid+1,rr,kk*2+1);
    }
    return final;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;++i)
    {
        cin>>a[i];
    }
    build(1,n,1);
    for(int i=2;i<=n;++i)
    {
        a[i]=a[i]-a[i-1];
    }
    a[1]=0;
    int num,x,y,k;
    for(int i=1;i<=m;++i)
    {
        cin>>num;
        if(num==1)
        {
            cin>>x>>y>>k;
            a[x]+=k;
            a[y+1]-=k;
        }
        else
        {
            cin>>x>>y;
            int cgm=0;
            for(int j=x;j<=y;++j)
            {
                cgm+=a[x];
            }
            cgm+=add(x,y,1);
            cout<<cgm<<endl;
        }
    }
    return 0;
}

by danlao @ 2024-02-11 13:02:28

@大海中的孤帆 你的线段树写错了，这是我的代码，你对照一下

#include <iostream>
#define int long long
using namespace std;
#define FOR(i,j,n,k) for(int i=(j);i<=(n);i+=k)
#define ROR(i,j,n,k) for(int i=(j);i>=(n);i-=k)
const int N1=1000010,N2=2000010;
int n,m;
int a[N1],b[N2],dp[N2];//tree;
void build(int l,int r,int now){
    if(l==r) {
        dp[now]=a[l];
        return;
    }
    int son=(l+r)/2;
    build(l,son,2*now),build(son+1,r,2*now+1);
    dp[now]=dp[now*2+1]+dp[now*2]; 
}
void update(int l,int r,int s,int t,int p,int c){
    if(l<=s&&t<=r){
        dp[p]+=(t-s+1)*c;
        b[p]+=c;
        return;
    }
    int m=s+((t-s)>>1);
    if(b[p]){
        dp[p<<1]+=b[p]*(m-s+1);
        dp[(p<<1)+1]+=b[p]*(t-m);
        b[p<<1]+=b[p],b[(p<<1)+1]+=b[p];
    }
    b[p]=0;
    if(l<=m) update(l,r,s,m,p<<1,c);
    if(r>m) update(l,r,m+1,t,(p<<1)+1,c);
    dp[p]=dp[p<<1]+dp[(p<<1)+1];
}
int getsum(int l,int r,int s,int t,int p){
    if(l<=s&&t<=r) return dp[p];
    int m=s+((t-s)>>1);
    if(b[p]){
        dp[p<<1]+=b[p]*(m-s+1);
        dp[(p<<1)+1]+=b[p]*(t-m);
        b[p<<1]+=b[p],b[(p<<1)+1]+=b[p];
    }
    b[p]=0;
    int sum=0;
    if(l<=m) sum+=getsum(l,r,s,m,p<<1);
    if(r>m) sum+=getsum(l,r,m+1,t,(p<<1)+1);
    return sum;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(),cout.tie();
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    cin>>n>>m;
    FOR(i,1,n,1) cin>>a[i];
    build(1,n,1);
    FOR(i,1,m,1){
        int op,l,r,x;
        cin>>op>>l>>r;
        if(op==1){
            cin>>x;
            update(l,r,1,n,1,x);
        }else{
            cout<<getsum(l,r,1,n,1)<<endl;
        }
    }
    return 0;
}

by 大海中的孤帆 @ 2024-02-11 15:52:39

@yaodiguoan 好的

by 大海中的孤帆 @ 2024-02-11 15:53:16

ios::sync_with_stdio(0);

这是啥

by danlao @ 2024-02-11 17:36:35

@大海中的孤帆 关同步流，用来加速cin/cout的，但用了这个就用不了scanf/printf，但这是cin/cout通常没有快读快写快

快读快写板子

inline void read(int &n){
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    n=x*f;
}

inline void write(int x){
    if(x<0){putchar('-');x=-x;}
    if(x>9)write(x/10);
    putchar(x%10+'0');
}

by hair_loss_tree @ 2024-02-12 09:16:31

卷死你