[ABC371D] 1D Country 线段树解法

其实这题还可以用值域线段树来做的。。。

考虑到 \([-1e9,1e9]\) 的数据范围，则一般的线段树绝对会MLE，但同时我们注意到点的个数只有 \(2e5\) 个，考虑使用动态开点线段树。

即对于每个村庄，看做一个点，所以我们的线段树无需模拟满二叉树。

由于 \(log_2(2e9)\approx30\) ，所以我们的线段树数组需要至少开到 \(30 \times 2e5 = 6e6\) 。

代码：

#include <bits/stdc++.h>
#define seq(q, w, e) for (int q = w; q <= e; q++)
#define ll long long
using namespace std;
const int maxn = 6e6+10,maxx=2e5+10;
const int limt=1e9+10;
#define lson tree[p].ls
#define rson tree[p].rs
ll n,m;
ll tot,rt;                          //tot为点数，rt为根节点
ll posx[maxx];                      //村庄位置
struct node{
    ll ls,rs,sum;                   //sum为人口数
}tree[maxn];
void push_up(ll p){
    tree[p].sum=tree[lson].sum+tree[rson].sum;  //本质为求和线段树
}
void insert(ll pos,ll &p,ll l,ll r,ll d){       //插入点
    if(!p){                                     //开新的点
        p=++tot;
        lson=rson=tree[p].sum=0;                //初始化
    }
    if(l==r){
        tree[p].sum+=d;                         //维护人口
        return;
    }
    ll mid=(l+r)>>1;
    if(pos<=mid) insert(pos,lson,l,mid,d);      //递归寻找
    else       insert(pos,rson,mid+1,r,d);
    push_up(p);
}
ll query(ll l,ll r,ll p,ll pl,ll pr){
    if(!p) return 0;                            //若不存在
    if(l<=pl&&r>=pr) return tree[p].sum;        //下为正常线段树的求和函数
    ll res=0,mid=(pl+pr)>>1;
    if(l<=mid) res+=query(l,r,lson,pl,mid);
    if(r>mid) res+=query(l,r,rson,mid+1,pr);
    return res;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    seq(i,1,n){
        cin>>posx[i];
    }
    seq(i,1,n){
        ll op;
        cin>>op;
        insert(posx[i],rt,-limt,limt,op);       //在值域中插入点
    }
    cin>>m;
    seq(i,1,m){
        int l,r;
        cin>>l>>r;
        cout<<query(l,r,rt,-limt,limt)<<"\n";  //区间查询
    }
    return 0;
}