RT,感觉写的没有问题,BIT 也初始化了。来个好心人救一下啊。
#include<bits/stdc++.h>
#define int long long
#define ctz __builtin_ctz
using namespace std;
const int maxn=3e5+7;
int n,q;
int x[maxn];
int w[maxn];
inline int lb(int x){return x&-x;}
struct BIT{
int t[maxn];
void upd(int x,int c){
while(x){
t[x]=min(t[x],c);
x-=lb(x);
}
}
int qry(int x){
int ans=4e18;
while(x<=n){
ans=min(ans,t[x]);
x+=lb(x);
}
return ans;
}
}T;
struct que{
int l,id;
};
struct rng{
int l,c;
};
struct node{
int id,wei;
};
vector<que> QR[maxn];
vector<rng> RG[maxn];
node p[maxn];
int ans[maxn];
stack<node> st;
int calc(int i,int j){
return abs(x[i]-x[j])*(w[i]+w[j]);
}
signed main(){
memset(T.t,0x3f,sizeof(T.t));
cin>>n>>q;
for(int i=1;i<=n;i++){
cin>>x[i]>>w[i];
p[i]=(node){i,w[i]};
}
for(int i=1;i<=q;i++){
int l,r;
cin>>l>>r;
QR[r].push_back((que){l,i});
}
for(int i=1;i<=n;i++){
while(!st.empty()&&st.top().wei>p[i].wei){
int c=calc(p[i].id,st.top().id);
RG[i].push_back((rng){st.top().id,c});
st.pop();
}
st.push(p[i]);
}
while(!st.empty())st.pop();
for(int i=n;i>=1;i--){
while(!st.empty()&&st.top().wei>p[i].wei){
int c=calc(p[i].id,st.top().id);
RG[st.top().id].push_back((rng){i,c});
st.pop();
}
st.push(p[i]);
}
for(int i=1;i<=n;i++){
for(int j=0;j<RG[i].size();i++){
T.upd(RG[i][j].l,RG[i][j].c);
}
for(int j=0;j<QR[i].size();i++){
ans[QR[i][j].id]=T.qry(QR[i][j].l);
}
}
// cout<<"ANS"<<endl;
for(int i=1;i<=q;i++){
cout<<ans[i]<<endl;
}
}