样例输出全0求调
查看原帖
样例输出全0求调
906856
A2_Zenith楼主2023/12/23 19:25

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;
	}
}
2023/12/23 19:25
加载中...