洛谷——P2781 传教

P2781 传教

题意很简单，就是要求你写一个数据结构，支持区间加法和区间查询

显然，线段树模板嘛。。。

不过$n<=10^9$，惊呆世人，啊哈，灵光一现，分块貌似可做，emmmm有感觉不行，$nlogn$？

线段树空间是炸掉了，RE $50$分

#include<bits/stdc++.h>

#define  N 100000000
using namespace std;

struct node{
    int l,r,w,f;
}tr[N];

int n,m;

void build(int k,int l,int r){
    tr[k].l=l,tr[k].r=r;
    if(l==r) return;
    int mid=(l+r)>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
}

void push(int k){
    if(tr[k].f){
        tr[k<<1].w+=(tr[k<<1].r-tr[k<<1].l+1)*tr[k].f;
        tr[k<<1].f+=tr[k].f;
        
        tr[k<<1|1].w+=(tr[k<<1|1].r-tr[k<<1|1].l+1)*tr[k].f;
        tr[k<<1|1].f+=tr[k].f;
        
        tr[k].f=0;
    }
}
void push_down(int k){
    tr[k].w=tr[k<<1].w+tr[k<<1|1].w;
}
void add(int k,int ql,int qr,int val){
    int l=tr[k].l,r=tr[k].r,mid=(l+r)>>1;
    if(l>=ql&&r<=qr) {tr[k].w+=(r-l+1)*val;tr[k].f+=val;return;}
    push(k);
    if(ql<=mid) add(k<<1,ql,qr,val);
    if(qr>mid) add(k<<1|1,ql,qr,val);
    push_down(k);
}

int ask(int k,int ql,int qr){
    int l=tr[k].l,r=tr[k].r,mid=(l+r)>>1;
    if(l>=ql&&r<=qr) return tr[k].w;
    push(k);
    int ans=0;
    if(ql<=mid) ans+=ask(k<<1,ql,qr);
    if(qr>mid) ans+=ask(k<<1|1,ql,qr);
    push_down(k);
    return ans;
}

int main()
{
    scanf("%d%d",&n,&m);
    build(1,1,n);
    for(int opt,l,r,x,i=1;i<=m;i++){
        scanf("%d%d%d",&opt,&l,&r);
        if(opt==2) printf("%d
",ask(1,l,r));
        else scanf("%d",&x),add(1,l,r,x);
    }
    
    return 0;
}

转大佬博客

动态开点线段树，指针写的，只好用指针，学习一下

#include<bits/stdc++.h>

#define  N 100000000
#define LL long long
using namespace std;

struct node {
    LL w,f;
    node *lc,*rc;
    node() {
        w=f=0,lc=rc=NULL;
    }
    void push_up() {
        w=0;
        if(lc) w+=lc->w;
        if(rc) w+=rc->w;
    }
    void push_down(int l,int r){
        if(!lc) lc=new node();
        if(!rc) rc=new node();
        int mid=(l+r)>>1;
        lc->w+=(mid-l+1)*f,lc->f+=f;
        rc->w+=(r-mid)*f,rc->f+=f;
        f=0;
    }
}*root=new node();

int n,m,tot;

void add(node *rt,int l,int r,int ql,int qr,LL val) {
    if(l>=ql&&r<=qr) {
        rt->w+=(r-l+1)*val;
        rt->f+=val;
        return;
    }
    rt->push_down(l,r);
    int mid=(l+r)>>1;
    if(ql<=mid) add(rt->lc,l,mid,ql,qr,val);
    if(qr>mid) add(rt->rc,mid+1,r,ql,qr,val);
    rt->push_up();
}

LL ask(node *rt,int l,int r,int ql,int qr) {
    if(l>=ql&&r<=qr) return rt->w;
    rt->push_down(l,r);
    LL ans=0;
    int mid=(l+r)>>1;
    if(ql<=mid) ans+=ask(rt->lc,l,mid,ql,qr);
    if(qr>mid) ans+=ask(rt->rc,mid+1,r,ql,qr);
    rt->push_up();
    return ans;
}

int main() {
    scanf("%d%d",&n,&m);
    for(int opt,l,r,x,i=1; i<=m; i++) {
        scanf("%d%d%d",&opt,&l,&r);
        if(opt==2) printf("%lld
",ask(root,1,n,l,r));
        else scanf("%d",&x),add(root,1,n,l,r,x);
    }

    return 0;
}

由于此题$m<=10^3$询问极少，可以暴力枚举前面的的区间