[BJOI2016] 回转寿司

emmmm慢慢捡回来以前学的东西，先从水题开始写吧。记录一下动态开点权值线段树模板
大概就是把式子化简一下,用s[i]表示a[i]的前缀和某一段区间的和处于[l,r]则是s[R]-l \le s[L] \le s[R]-r 那么就是每次查询[s[R]-l,s[R]-r]中间有多少权值，然后再将s[R]添加到线段树中。由于权值范围很大，但是权值的个数不多，于是可以采用动态开点的技巧节约空间。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#define maxn 100010
#define N 10000000000
#define ll long long
#define mid ((l+r)>>1)
using namespace std;
int n,l,r;
ll a[maxn];
struct segtree;
segtree *Nul;
struct segtree{
    int sum;
    segtree *so[2];
    segtree(){
        sum=0;
        so[0]=so[1]=Nul;
    }
    void new_point(){
        if(so[0]==Nul) so[0]=new segtree;
        if(so[1]==Nul) so[1]=new segtree;
    }
    void update(){
        sum=so[0]->sum+so[1]->sum;
    }
    void modify(ll l,ll r,ll pos){
        if(l==r){
            sum+=1;
            return;
        }
        new_point();
        bool b=pos>mid;
        if(b) l=mid+1; else r=mid;
        so[b]->modify(l,r,pos);
        update();
    }
    ll query(ll l,ll r,ll lx,ll rx){
        if(l==lx&&r==rx) return sum;
        if(rx<=mid) return so[0]->query(l,mid,lx,rx);
        else if(lx>mid) return so[1]->query(mid+1,r,lx,rx);
        else return so[0]->query(l,mid,lx,mid)+so[1]->query(mid+1,r,mid+1,rx);
        return 0;
    }
}*xtr;
void get_ready(){
    Nul=new segtree;
    xtr=new segtree;
    Nul->so[0]=Nul;
    Nul->so[1]=Nul;
    Nul->sum=0;
}
ll ans;
int main(){
    get_ready();
    scanf("%d%d%d",&n,&l,&r);
    for(int i=1;i<=n;++i) scanf("%lld",&a[i]);
    for(int i=1;i<=n;++i) a[i]+=a[i-1];
    for(int i=0;i<=n;++i){
        ans+=xtr->query(-N, N, a[i]-r, a[i]-l);
        xtr->modify(-N, N, a[i]);
    }
    cout<<ans;
    return 0;
}