标记下传线段树 0tps 求调，悬关

JoyLosingK @ 2024-08-20 11:30:56

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define mid (l+r>>1)
const int N=1e5+7;
int a[N],sum[N*4],add[N*4],m,op,t,g,c,n;
inline int read(){
    int x=0,f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
    return x*f;}
void maketree(int k,int l,int r){
    if(l==r){sum[k]=a[r];return;}
    maketree(k<<1,l,mid),maketree(k<<1|1,mid+1,r);
    sum[k]=sum[k<<1]+sum[k<<1|1]; return;}
void Add(int k,int l,int r,int v){
    add[k]+=v,sum[k]+=(r-l+1)*v; return;}
void pushdown(int k,int l,int r){
    if(!add[k]) return;
    Add(k<<1,l,mid,add[k]),Add(k<<1|1,mid+1,r,add[k]);
    add[k]=0; return;}
void modifly(int k,int l,int r,int x,int y,int v){
    if(r<x||y<l) return;
    if(l>=x&&r<=y){Add(k,l,r,v);return;} 
    pushdown(k,l,r);
    if(x<=mid) modifly(k<<1,l,mid,x,y,v);
    if(mid<y)  modifly(k<<1|1,mid+1,r,x,y,v);
    sum[k]=sum[k<<1]+sum[k<<1|1]; return;}
int query(int k,int l,int r,int x,int y){
    if(r<x||y<l) return 0;
    if(l>=x&&r<=y) return sum[k];
    int res=0; pushdown(k,l,r);
    if(x<=mid) res+=query(k<<1,l,mid,x,y);
    if(mid<y)  res+=query(k<<1|1,mid+1,r,x,y);
    return res;}
main()
{   n=read(),m=read();
    for(int i=1;i<=n;i++) a[i]=read();
    maketree(1,1,n);
    while(m--){ op=read();
        if(op==1)modifly(1,1,n,t=read(),g=read(),c=read());
        else cout<<query(1,1,n,t=read(),g=read())<<endl;
    } return 0;
}

by cj180202 @ 2024-08-20 11:43:54

什么逆天马蜂

by 2024hyx @ 2024-08-20 11:44:55

@JoyLosingK

输入的锅，改一下就过了。

比如modifly(1,1,n,t=read(),g=read(),c=read());，他是从c开始读入的，与题意不符。

ac代码

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define mid (l+r>>1)
const int N=1e5+7;
int a[N],sum[N*4],add[N*4],m,op,l,r,n;
inline int read(){
    int x=0,f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
    return x*f;}
void maketree(int k,int l,int r){
    if(l==r){sum[k]=a[r];return;}
    maketree(k<<1,l,mid),maketree(k<<1|1,mid+1,r);
    sum[k]=sum[k<<1]+sum[k<<1|1]; return;}
void Add(int k,int l,int r,int v){
    add[k]+=v,sum[k]+=(r-l+1)*v;}
void pushdown(int k,int l,int r){
    if(!add[k]) return;
    Add(k<<1,l,mid,add[k]),Add(k<<1|1,mid+1,r,add[k]);
    add[k]=0;}
void modifly(int k,int l,int r,int x,int y,int v){
    if(l>=x&&r<=y){Add(k,l,r,v);return;} 
    pushdown(k,l,r);
    if(x<=mid) modifly(k<<1,l,mid,x,y,v);
    if(mid<y)  modifly(k<<1|1,mid+1,r,x,y,v);
    sum[k]=sum[k<<1]+sum[k<<1|1];}
int query(int k,int l,int r,int x,int y){
    if(l>=x&&r<=y) return sum[k];
    int res=0; pushdown(k,l,r);
    if(x<=mid) res+=query(k<<1,l,mid,x,y);
    if(mid<y)  res+=query(k<<1|1,mid+1,r,x,y);
    return res;}
main()
{   n=read(),m=read();
    for(int i=1;i<=n;i++) a[i]=read();
    maketree(1,1,n);
    while(m--){ op=read(),l=read(),r=read();
        if(op==1)modifly(1,1,n,l,r,read());
        else cout<<query(1,1,n,l,r)<<endl;
    } return 0;
}

求个关注

by JoyLosingK @ 2024-08-20 15:58:34

@2024hyx

已关，谢谢大佬