本文共 1338 字，大约阅读时间需要 4 分钟。
分析
我们多维护一个值，代表某个点子树中所有点的权值和
于是如果某个点它的min和max乘a(/b)的值小于范围则直接把整个子树都加进去
估价函数就是这个点的子树中的理论最小值
代码
#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define int long longconst int inf = 1e9;inline int ra(){ int x=0,f=1;char s=getchar(); while(!isdigit(s)){ if(s=='-')f=-1;s=getchar();} while(isdigit(s))x=(x<<3)+(x<<1)+(s-'0'),s=getchar(); return x*f;}struct kd { int d[2],mx[2],mn[2],le,ri,id,sum,val;};kd t[300100],now;int n,m,root,wh,Ans;inline bool operator < (kd a,kd b){ return a.d[wh] >1; x=mid; nth_element(t+le,t+x,t+ri+1); for(int i=0;i<2;++i) t[x].mn[i]=t[x].mx[i]=t[x].d[i]; if(le x)build(t[x].ri,mid+1,ri,wwh^1); up(x);}inline int getd(kd a,kd b){ if(!a.id)return inf; int res=0; for(int i=0;i<2;++i)res+=a.d[i]*b.d[i]; return res;}inline int calc(int x){ if(!x)return inf; int res=0; for(int i=0;i<2;++i) res+=min(t[x].mn[i]*now.d[i],t[x].mx[i]*now.d[i]); return res;}inline int getmax(int x){ if(!x)return inf; int res=0; for(int i=0;i<2;++i) res+=max(t[x].mn[i]*now.d[i],t[x].mx[i]*now.d[i]); return res;}inline void qurey(int x){ if(!x)return; if(getmax(x)
转载于:https://www.cnblogs.com/yzxverygood/p/10562729.html