求助代码厌氧,开了O2可以过,不开会wa第二个点
查看原帖
求助代码厌氧,开了O2可以过,不开会wa第二个点
524801
不食嗟来之食楼主2022/10/15 20:07
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
const int N=2e4,M=1E7+5;
struct pe{
	int l,r;
	long long sum1,sum2;
}a[M<<2];
int n;
struct peo{
	long long v;
	long long x;
}b[N];
bool cmp(peo ax,peo bx){
	return ax.v<bx.v;
}
#define lson k<<1
#define rson k<<1|1
void push_up(int k){
	a[k].sum1=a[lson].sum1+a[rson].sum1;
	a[k].sum2=a[lson].sum2+a[rson].sum2;
	return ;
}
void build(int k,int l,int r){
	a[k].l=l,a[k].r=r;
	if(l==r) return ;
	int mid=(l+r)>>1;
	build(lson,l,mid);
	build(rson,mid+1,r);
	return ;
}
int get(int k,int l,int r,int opt){
	if(a[k].l>=l&&a[k].r<=r){
		if(opt==1) return a[k].sum1;
		if(opt==2) return a[k].sum2;
	}
	int mid=(a[k].l+a[k].r)>>1;
	int ans=0;
	if(l<=mid) ans+=get(lson,l,r,opt);
	if(r> mid) ans+=get(rson,l,r,opt);
	return ans;
}
void add(int k,int x,long long y){
	if(a[k].l==a[k].r){
		a[k].sum1+=y;
		a[k].sum2++;
		return ;
	}
	if(x<=a[lson].r) add(lson,x,y);
	else add(rson,x,y);
	push_up(k);
	return ;
}
long long ans;
long long maxn;
int main(){
//	freopen("P2345_2.in","r",stdin);
	scanf("%d",&n);
	for(int i=1;i<=n;i++){scanf("%lld%lld",&b[i].v,&b[i].x);maxn=max(maxn,b[i].x);}
	sort(b+1,b+1+n,cmp);
	build(1,1,maxn);
	for(int i=1;i<=n;i++){
		long long g=get(1,b[i].x+1,maxn,1);
		long long k=get(1,b[i].x+1,maxn,2);
//		printf("%lld %lld\n",g,k);
		ans+=b[i].v*(g-k*b[i].x);
		g=get(1,1,b[i].x-1,1);
		k=get(1,1,b[i].x-1,2);
		ans+=b[i].v*(k*b[i].x-g);
		add(1,b[i].x,b[i].x);
//		printf("%lld %lld\n",a[1].sum1,a[1].sum2);
	}
	printf("%lld\n",ans);
	return 0;
}

线段树写法qwq

2022/10/15 20:07
加载中...