本文移植自个人的原博客（原文）

题目链接

Functions On The Segments

题目描述

题目描述

题解

题目大意为给定$n$个函数，求将$x$代入连续的一段函数中所得的值的和，强制在线。

考虑将求和信息更改为代入$(1,r)$中所得答案与代入$(1,l−1)$所得答案相减，那么问题变可以通过主席树进行实现，每一个函数以下具有两种形式。

1.

$y_1, \ if \ x \leq x_1$
$b, \ if \ x_1 < x \leq x_2$
$y_2, \ if \ x_2 < x$

2.

$a * x, \ if \ x_1 < x \leq x_2$

对于这两种形式各建一颗主席树，分别求和。需要注意该题可以直接将标记永久化，则不需要过于主席树中繁琐的pushdown。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+1;
const int M = N*81;
const int lim = 2e5+1;
const ll mod = 1e9;
int n,q;
struct Chairman_Tree
{
    int rt[N],lc[M],rc[M];
    ll w[M];
    int tot;
    void init(){tot=0;}
    int build(int l,int r)
    {
        int x=++tot;
        w[x]=0;
        if(l==r) return x;
        int mid=(l+r)>>1;
        lc[x]=build(l,mid);
        rc[x]=build(mid+1,r);
        return x;
    }
    int update(int x,int l,int r,int y1,int y2,int val)
    {
        int y=++tot;
        w[y]=w[x];lc[y]=lc[x];rc[y]=rc[x];
        if(y1<=l&&y2>=r)
        {
            w[y]+=val;
            return y;
        }
        int mid=(l+r)>>1;
        if(y1<=mid) lc[y]=update(lc[x],l,mid,y1,y2,val);
        if(y2>mid) rc[y]=update(rc[x],mid+1,r,y1,y2,val);
        return y;
    }
    ll query(int x,int l,int r,int pos)
    {
        if(l==r) return w[x];
        int mid=(l+r)>>1;
        if(pos<=mid) return query(lc[x],l,mid,pos)+w[x];
        else return query(rc[x],mid+1,r,pos)+w[x];
    }
}T[2];
int main()
{
    for(int i=0;i<2;++i) 
    {
        T[i].init();
        T[i].rt[0]=T[i].build(0,lim);
    }
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        int xx1,xx2,yy1,a,b,yy2;
        scanf("%d%d%d%d%d%d",&xx1,&xx2,&yy1,&a,&b,&yy2);
        int tmp;
        tmp=T[0].update(T[0].rt[i-1],0,lim,0,xx1,yy1);
        tmp=T[0].update(tmp,0,lim,xx1+1,xx2,b);
        T[0].rt[i]=T[0].update(tmp,0,lim,xx2+1,lim,yy2);
        T[1].rt[i]=T[1].update(T[1].rt[i-1],0,lim,xx1+1,xx2,a);
    }
    int q;
    scanf("%d",&q);
    ll ans=0;
    while(q--)
    {
        int l,r,x;
        scanf("%d%d%d",&l,&r,&x);
        x=(x+ans)%mod;
        int lx=min(x,lim);
        ans=0;
        ans+=T[0].query(T[0].rt[r],0,lim,lx)-T[0].query(T[0].rt[l-1],0,lim,lx);
        ans+=x*(T[1].query(T[1].rt[r],0,lim,lx)-T[1].query(T[1].rt[l-1],0,lim,lx));
        printf("%I64d\n",ans);
    }
    return 0;
}
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+1;
int w[N],a[N],add[N];
void up(int x){w[x]=w[x<<1]+w[x<<1|1];}
void build(int x,int l,int r)
{
    if(l==r)
    {
        w[x]=a[l];
        return;
    }
    int mid=l+r>>1;
    build(x<<1,l,mid);build(x<<1|1,mid+1,r);
    up(x);
}

void upd(int x,int l,int r,int L,int R,int d)
{
    if(L<=l&&r<=R){add[x]+=d;return;}
    w[x]+=d*(R-L+1);
    int mid=l+r>>1;
    if(L<=mid)upd(x<<1,l,mid,L,R,d);
    if(R>mid)upd(x<<1|1,mid+1,r,L,R,d);
    return;
}

int query(int x,int l,int r,int L,int R)
{
    int ret=add[x]*(R-L+1);
    if(L<=l&&r<=R){return ret+w[x];}
    int mid=l+r>>1;
    if(L<=mid)ret+=query(x<<1,l,mid,L,R);
    if(R>mid)ret+=query(x<<1|1,mid+1,r,L,R);
    return ret;
}
int n,m;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)scanf("%d",a+i);
    build(1,1,n);
    for(int i=1,q,x,y,k;i<=m;++i)
    {
        scanf("%d",&q);
        if(q==1)
        {
            scanf("%d%d%d",&x,&y,&k);
            upd(1,1,n,x,y,k);
        }
        if(q==2)
        {
            scanf("%d%d",&x,&y);
            printf("%d\n",query(1,1,n,x,y));
        }
    }
}