题解 P1438 【无聊的数列】

· · 题解

Solution

　　发现数列一开始的的值根本不用管诶, 所以我们维护的不过就是这个数列的部分所具有的等差的性质而已.

　　所以标记根本不用下放, 也就是标记永久化.我们看标记维护的是啥, 首先标记维护这个区间被加上的等差数列的性质, 因为等差数列具有可加性.所以在一个等差数列上加上一个等差数列仍然是一个等差数列, 因此标记可以这样写:

struct Flag{
    int l,r,k,d;
    Flag(){l=r=k=d=0;}
    Flag(int a,int b,int c,int e){l=a,r=b,k=c,d=e;}
    int val(int p){
        if(p>r||p<l)return false;
        return k+(p-l)*d;
    }
    int update(int L,int R,Flag o){
        k+=(L-o.l)*o.d+o.k,d+=o.d,l=L,r=R;
    }
};

　　如何查询某个位置的值呢?用数列原本这个位置的值加上等差数列的值.也就是在线段树中查找\log_2 n层, 将每层标记中的等差数列加上就是这个位置的值.

Code

指针线段树

#include<cstdio>
#define N 100005
using namespace std;

struct Flag{
    int l,r,k,d;
    Flag(){l=r=k=d=0;}
    Flag(int a,int b,int c,int e){l=a,r=b,k=c,d=e;}
    int val(int p){
        if(p>r||p<l)return false;
        return k+(p-l)*d;
    }
    int update(int L,int R,Flag o){
        k+=(L-o.l)*o.d+o.k,d+=o.d,l=L,r=R;
    }
};

struct Node{
    Flag f;
    Node *ls,*rs;
    Node(){}
}pool[N<<1];
Node* new_Node(){
    static int cnt=0;
    return &pool[cnt++];
}

void build(int l,int r,Node *now){
    if(l==r)return ;
    int mid=(l+r)>>1;
    now->ls=new_Node(),now->rs=new_Node();
    build(l,mid,now->ls);
    build(mid+1,r,now->rs);
}

void Modify(int l,int r,Flag o,Node* now){
    if(l>=o.l&&r<=o.r){now->f.update(l,r,o);return ;}
    int mid=(l+r)>>1;   
    if(o.l<=mid)Modify(l,mid,o,now->ls);
    if(o.r>mid)Modify(mid+1,r,o,now->rs);
}

int query(int l,int r,int p,Node* now){
    int ans=now->f.val(p);
    if(l==r)return ans;
    int mid=(l+r)>>1;
    if(p<=mid)return ans+query(l,mid,p,now->ls);
    else return ans+query(mid+1,r,p,now->rs);
}

int s[N];

int main(){
    int n,m;Node *root=new_Node();
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
        scanf("%d",&s[i]);
    build(1,n,root);
    int a,b,c,d,e;
    while(m--){
        scanf("%d",&a);
        if(a==1){
            scanf("%d%d%d%d",&b,&c,&d,&e);
            Modify(1,n,(Flag){b,c,d,e},root);
        }
        else {
            scanf("%d",&b);
            printf("%d",s[b]+query(1,n,b,root));
        }
    }
    return 0;
}