#pragma once
#include"../segment-tree/segment-tree.hpp"// S ... index_type// T ... value_type// F ... function_typetemplate<typenameS,typenameT,typenameF>structRangeTree{usingSeg=SegmentTree<T,F>;usingP=pair<S,S>;SN,M;constFf;Tti;vector<SegmentTree<T,F>>seg;vector<vector<S>>ys;vector<P>ps;RangeTree(constF&f_,constT&ti_):f(f_),ti(ti_){}voidadd_point(Sx,Sy){ps.push_back(make_pair(x,y));}voidbuild(){sort(begin(ps),end(ps));ps.erase(unique(begin(ps),end(ps)),end(ps));N=ps.size();for(inti=0;i<2*N;++i)seg.push_back(Seg{f,ti});ys.resize(2*N);for(inti=0;i<N;++i){ys[i+N].push_back(ps[i].second);seg[i+N].init(1);}for(inti=N-1;i>0;--i){ys[i].resize(ys[i<<1].size()+ys[(i<<1)|1].size());merge(begin(ys[(i<<1)|0]),end(ys[(i<<1)|0]),begin(ys[(i<<1)|1]),end(ys[(i<<1)|1]),begin(ys[i]));ys[i].erase(unique(begin(ys[i]),end(ys[i])),end(ys[i]));seg[i].init(ys[i].size());}}intid(Sx)const{returnlower_bound(begin(ps),end(ps),make_pair(x,S()),[](constP&a,constP&b){returna.first<b.first;})-begin(ps);}intid(inti,Sy)const{returnlower_bound(begin(ys[i]),end(ys[i]),y)-begin(ys[i]);}voidadd(Sx,Sy,Ta){inti=lower_bound(begin(ps),end(ps),make_pair(x,y))-begin(ps);assert(ps[i]==make_pair(x,y));for(i+=N;i;i>>=1)seg[i].add(id(i,y),a);}Tsum(Sxl,Syl,Sxr,Syr){TL=ti,R=ti;inta=id(xl),b=id(xr);for(a+=N,b+=N;a<b;a>>=1,b>>=1){if(a&1)L=f(L,seg[a].query(id(a,yl),id(a,yr))),++a;if(b&1)--b,R=f(seg[b].query(id(b,yl),id(b,yr)),R);}returnf(L,R);}};/*
* @brief 領域木(Segment Tree)
*/