日常求找错

回复帖子

@_zyx_ 2019-08-14 09:22 回复

RT

样列输出全是4(电脑炸了调试不了)

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
inline long long  read()
{
    char ch=getchar(); 
    long long  x=0,f=1;
    while((ch>'9'||ch<'0')&&ch!='-')
        ch=getchar();
    if(ch=='-')
    {
        f=-1;
        ch=getchar();
    }
    while('0'<=ch&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
long long  n,m;
long long  a[100005];
struct tT
{
    long long  lazytag;
    long long  sum;
}tree[100000*4];
void build(long long  i,long long  l,long long  r)
{
    if(l==r)
    {
        tree[i].sum=a[l];
        return;
    }
    long long  mid=(l+r)>>1;
    build(i*2,l,mid);
    build(i*2+1,mid+1,r);
    tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;
}
void push_down(long long  i,long long  l,long long  r)
{
    long long  mid=(l+r)>>1;
    //l
    tree[i*2].lazytag+=tree[i].lazytag;
    tree[i*2].sum+=tree[i].lazytag*(mid-l+1);
    tree[i*2+1].lazytag+=tree[i].lazytag;
    tree[i*2+1].sum+=tree[i].lazytag*(r-mid);
}
void add(long long  nl,long long  nr,long long  l,long long  r,long long  i,long long  k)
{
    if(nr>=r&&nl<=l)
    {
        tree[i].sum+=k*(r-l+1);
        tree[i].lazytag+=k;
        return ;
    }
    push_down(i,l,r);
    long long  mid=(l+r)>>1;
    if(nl<=mid) add(nl,nr,l,mid,i*2,k);
    if(nr>mid)  add(nl,nr,mid+1,r,i*2+1,k);
    tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;
}
long long  getsum(long long  nl,long long  nr,long long  l,long long  r,long long  i)
{
    long long  sum=0;
    if(nl<=l&&nr>=r)
    {
        return tree[i].sum;
    }
    long long  mid=(l+r)>>1;
    push_down(i,l,r);
    if(nl<=mid)
    {
        sum+=getsum(nl,nr,l,mid,i*2);
    }
    if(nr>mid)
    {
        sum+=getsum(nl,nr,mid+1,r,i*2+1);
    }
}
int  main(int  argc, char const *argv[])
{
    n=read(),m=read();
    for(long long  i=1;i<=n;i++)
    {
        a[i]=read();
    }
    build(1,1,n);
    long long  in1,in2,in3,in4;
    for(long long  t=1;t<=m;t++)
    {
        in1=read();
        if(in1==1)
        {
            in2=read(),in3=read(),in4=read();
            add(in2,in3,1,n,1,in4);
        }
        else if(in1==2)
        {
            in3=read(),in4=read();
            cout<<getsum(in3,in4,1,n,1)<<endl;
        }
    }
    return 0;
}

主要是因为同机房的大佬成功在这里找到了错,我才了碰碰运气

不过我那么蒻应该没人理QAQ

@_zby_ 2019-08-14 09:23 回复 举报
#include<bits/stdc++.h>
#include<queue>
#define lc p<<1
#define rc p<<1|1
using namespace std;
inline void read(int &x)
{
    x=0;int k=1; char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')k=-1;c=getchar();}
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
    x*=k;
}//快读
struct tree{
    int sum,tag;
}a[1000001];
int data[1000001];
void push_up(int p){
    a[p].sum=a[lc].sum+a[rc].sum;
}
void push_down(int p,int l,int r){
    if(!a[p].tag)return;
    int mid=(l+r)>>1;
    a[lc].tag+=a[p].tag;
    a[rc].tag+=a[p].tag;
    a[lc].sum+=(mid-l+1)*a[p].tag;
    a[rc].sum+=(r-mid)*a[p].tag;
    a[p].tag=0; 
}
void build(int p,int l,int r){
    if(l==r){a[p].sum=data[l];return;}
    int mid=(l+r)>>1;
    build(lc,l,mid);
    build(rc,mid+1,r);
    push_up(p);
}
void add(int p,int l,int r,int L,int R,int k){
    if(l>=L&&r<=R){a[p].sum+=(r-l+1)*k;a[p].tag+=k;return;}
    push_down(p,l,r);
    int mid=(l+r)>>1;
    if(L<=mid)add(lc,l,mid,L,R,k);
    if(R>mid)add(rc,mid+1,r,L,R,k);
    push_up(p);
}
int query(int p,int l,int r,int L,int R){
    if(l>=L&&r<=R)return a[p].sum;
    push_down(p,l,r);
    int mid=(l+r)>>1,ans=0;
    if(L<=mid)ans+=query(lc,l,mid,L,R);
    if(R>mid)ans+=query(rc,mid+1,r,L,R);
    return ans;
}
int main(){
    int n,m;
    int q;
    read(n);read(m);
    for(long long i=1;i<=n;i++)
    read(data[i]);
    build(1,1,n);
    while(m--){
        read(q);
        if(q==1) {
            int x,y,k;
            read(x);read(y);read(k);
            add(1,1,n,x,y,k);
        }
        else{
            int x,y;
            read(x);read(y);
            cout<<query(1,1,n,x,y)<<endl;
        }
    }
    return 0;
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。