D. Pair of Topics
题意：给定ab序列，问i<j且ai+aj>bi+bj的对数。
转化：ai-bi<-(aj-bj)
一开始拿到题目想着sort，但是发现i<j这个条件就不敢想下去了。
然后想着然后倒着遍历，c记为a-b的值.每个c先在一个vector找到小于他的个数,然后把-1*c再插入。但是vector的insert让我tle哈哈
对于i<j限制条件的转化：
如果存在ci>-cj，那么必有cj>-ci
那么对于不同的ij而言，只要找到了就算一对，答案除以二就可以处理了
实现时候把差值c放在a数组里，c数组中放a数组的相反数。对c数组进行sort，再进行lowerbound（第一个小于等于）找出小于a[i]的元素个数。注意在找到的时候可能把自己和自己计算在内，也就是相同的ij，这个时候需要减去自己。如果差值ci>0，那么必然有ci>-ci，也就是在lowerbound中多记录了一个.
int a[maxn],c[maxn];int main(){int n=ird();LL ans=0;for(int i=1;i<=n;i++)a[i]=ird();for(int i=1;i<=n;i++){int tt=ird();a[i]-=tt;c[i]=-1*a[i];}sort(c+1,c+n+1);for(int i=1;i<=n;i++){int tt=min(n,lower_bound(c+1,c+1+n,a[i])-c);if(c[tt]>=a[i]&&a[i]!=0)tt--;if(a[i]>=0)tt--;//cout<<tt<<endl;ans+=(1ll*tt);}cout<<ans/2<<endl;return 0;}
二分tle待改进代码：
int main(){int n=ird();for(int i=1;i<=n;i++){//c[i].id=i;c[i].a=lrd();}vector<LL> mp;for(int i=1;i<=n;i++){c[i].b=lrd();c[i].d=c[i].a-c[i].b;}LL ans=0;mp.push_back(-2e9);mp.push_back(-1*c[n].d);int ii=n-1;while(ii>=1){int l=0,r=mp.size()-1;while(l<r){int mid=(l+r+1)/2;if(mp[mid]<c[ii].d){l=mid;}else r=mid-1;}ans+=l;l=0,r=mp.size()-1;while(l<r){int mid=(l+r+1)>>1;if(mp[mid]<-1*c[ii].d){l=mid;}elser=mid-1;}mp.insert(mp.begin()+l+1,1,-1*c[ii].d);ii--;}cout<<ans<<endl;return 0;}
