CCPC－Wannafly & Comet OJ 夏季欢乐赛（2019）F

灰太狼 2021-11-04 09:32 195阅读 0赞

[题面][Link 1]

F比较友善(相较于E)，我们发现如果i和j是满足条件的两个下标，那么:

a\[i\]-2\*b\[i\] + a\[j\]-2\*b\[j\] >=0 或者 b\[i\]-2\*a\[i\] + b\[j\]-2\*a\[j\] >=0。

又因为两个条件不可能同时成立(你把左边式子的不等号左边全移到右边试试)，所以我们可以分开算两种情况并最后把答案加起来。。。(其实两种情况是对称的，所以可以直接用一个函数解决，两次调用之间把所有 a\[\]与b\[\] swap一下就好啦)

对于每种情况，我们不妨把下标小的移项到右边，然后发现这就是一个简单的二维偏序问题啦，树状数组轻松过w

#include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    const int ha=1e9+7,N=1e5+5;
    
    int a[N],b[N],c[N],n,m,f[N*2];
    int p[N][2],num[N*2],ky,ans;
    
    inline int add(int x,int y){ x+=y; return x>=ha?x-ha:x;}
    inline void ADD(int &x,int y){ x+=y; if(x>=ha) x-=ha;}
    
    inline int read(){
        int x=0; char ch=getchar();
        for(;!isdigit(ch);ch=getchar());
        for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
        return x;
    }
    
    inline void update(int x,int y){
    	for(;x<=ky;x+=x&-x) ADD(f[x],y);
    }
    
    inline int query(int x){
    	int an=0;
    	for(;x;x-=x&-x) ADD(an,f[x]);
    	return an;
    }
    
    inline void solve(){
    	memset(f,0,sizeof(f)),ky=0;
    	
    	for(int i=1;i<=n;i++){
    		p[i][0]=a[i]-2*b[i],p[i][1]=-p[i][0];
    		num[++ky]=p[i][0],num[++ky]=p[i][1];
    	}
    	
    	sort(num+1,num+ky+1),ky=unique(num+1,num+ky+1)-num-1;
    	
    	for(int i=1;i<=n;i++)
    	    for(int j=0;j<2;j++) p[i][j]=lower_bound(num+1,num+ky+1,p[i][j])-num;
    	
    	for(int i=1;i<=n;i++) update(p[i][1],c[i]),ADD(ans,c[i]*(ll)query(p[i][0])%ha);
    }
    
    int main(){
    	n=read();
    	for(int i=1;i<=n;i++) a[i]=read(),b[i]=read(),c[i]=read();
    	
    	solve();
    	for(int i=1;i<=n;i++) swap(a[i],b[i]);
    	solve();
    	
    	printf("%d\n",ans);
    	return 0;
    }

转载于:https://www.cnblogs.com/JYYHH/p/11265788.html

[Link 1]: https://cometoj.com/contest/59/problem/F?problem_id=2681