题解 P4915 【帕秋莉的魔导书】

partychicken · 2018-10-09 20:44:09 · 题解

QAQ，不知道为啥写挂了，写篇题解理一下思路

先%同机房出题大佬，DSM tql

思路和他并不一样，QAQ。（这或许就是我wa的原因？？？）

以等级为下标，显然，只需要维护前缀和的区间和。

• 修改：单点加，放到前缀和里就是区间加（从当前位置加到末尾即可）
• 查询：对前缀和区间求和，然后除以区间长度

显然，用一个线段树维护前缀和数组就ok了。

由于等级范围很大，所以可以考虑离散化。然而蒟蒻不喜欢离线，所以写了动态开点。

代码。。。等我a了再说吧

upd:2018/10/9

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

struct SEG
{
    struct Node
    { 
        ll sum,add;
        int ls,rs;
        Node():sum(0),add(0),ls(0),rs(0){}
    }nd[2000010<<2];
    int cnt;
    SEG():cnt(1){}
    void pushdown(int x,int len)
    {
        if(nd[x].add)
        {
            int ls=(nd[x].ls?nd[x].ls:nd[x].ls=++cnt),rs=(nd[x].rs?nd[x].rs:nd[x].rs=++cnt);
            nd[ls].add+=nd[x].add,nd[ls].sum+=nd[x].add*(len-(len>>1));
            nd[rs].add+=nd[x].add,nd[rs].sum+=nd[x].add*(len>>1);
            nd[x].add=0;
        }
    }
    void update(int x)
    {
        nd[x].sum=nd[nd[x].ls].sum+nd[nd[x].rs].sum;
    }
    int modify(int x,int nl,int nr,int ql,int qr,ll val)
    {
        if(nl>qr||nr<ql) return 0;
        if(nl>=ql&&nr<=qr)
        {
            nd[x].add+=val,nd[x].sum+=val*(nr-nl+1);
            return 0;
        }
        pushdown(x,nr-nl+1);
        int mid=(long long)nl+nr>>1;
        !nd[x].ls?nd[x].ls=++cnt:0;modify(nd[x].ls,nl,mid,ql,qr,val);
        !nd[x].rs?nd[x].rs=++cnt:0;modify(nd[x].rs,mid+1,nr,ql,qr,val);
        update(x);
        return 0;
    }
    ll query(int x,int nl,int nr,int ql,int qr)
    {
        if(nl>qr||nr<ql) return 0;
        if(nl>=ql&&nr<=qr) return nd[x].sum;
        pushdown(x,nr-nl+1);
        int mid=(long long)nl+nr>>1;
        return (nd[x].ls?query(nd[x].ls,nl,mid,ql,qr):0)+(nd[x].rs?query(nd[x].rs,mid+1,nr,ql,qr):0);
    }
}seg;

const int inf=2147483646; 

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int v,w;
        cin>>v>>w;
        seg.modify(1,1,inf,v,inf,w);
    }
    for(int i=1;i<=m;i++)
    {
        int opt,v,w;
        cin>>opt>>v>>w;
        opt==1?(printf("%.4lf\n",(double)seg.query(1,1,inf,v,w)/(double)(w-v+1)),0):(seg.modify(1,1,inf,v,inf,w),0);
    }
}