cf1311F 树状数组，二维偏序

本文主要是介绍cf1311F 树状数组，二维偏序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

https://codeforces.com/contest/1311/problem/F

题意

数轴上有一些点，各个点有速度，问任两个点之间最短距离和

思路

a为位置(正),v为速度考虑i和j两个点，令ai<aj,容易发现只有vj>=vi时才能保证两个点不相遇，否则一定相遇。
对于相遇的点，他们的距离是0，否则距离为初始距离。
那么我们需要统计出所有ai<aj,vj>=vi的ij初始距离。

这个是一个标准的二维偏序。
说下什么是二维偏序，偏序是反对称，传递，自反的关系。二维偏序就是同时有两种偏序关系的情况。例如逆序对其实就是i<j且ai>aj这种二位偏序的关系的出现次数。具体维护做法就是先排序，之后利用数据结构进行维护就可以了。

回到这个题目，我们先排序，挨个插入当前的点，插入时考虑如何维护这个点和所有和他满足上文关系的点的距离和，我们利用类似前缀和的想法，我们利用两个树状数组，一个存放当前点到原点距离和，一个存放点的数目。每次插入当前点，他的贡献就是满足上文关系的点数目n*他到原点距离l-满足条件点到原点距离和L。

代码

#include<cstdio>
#include<iostream>
#include<set>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<string>
#include<queue>
#include<stack>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib> 
#include<chrono>
#include<bitset>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
#define int long long
//#define double long double
using namespace std;typedef long long ll;const int maxn=400505;const int inf=0x3f3f3f3f;int n,m,k;int a[maxn],b[maxn],c[maxn];int bit1[maxn],bit2[maxn];int lowbit(int x){return x&(-x);}void update(int i,int k,int *bit){while(i<maxn){bit[i]+=k;i+=lowbit(i);}}int getsum(int i,int *bit){int ans=0;while(i>0){ans+=bit[i];i-=lowbit(i);}return ans;}vector<pair<int,int>>v;void solve(){cin>>n;for(int i=1;i<=n;i++)	cin>>a[i];for(int i=1;i<=n;i++)	cin>>b[i],c[i]=b[i];sort(c+1,c+1+n);int len=unique(c+1,c+1+n)-c-1;for(int i=1;i<=n;i++)b[i]=lower_bound(c+1,c+1+len,b[i])-c;for(int i=1;i<=n;i++)	v.push_back({a[i],b[i]});sort(v.begin(),v.end());int ans=0;for(auto p:v){int cnt=getsum(p.second,bit2),le=getsum(p.second,bit1);ans+=cnt*p.first-le;update(p.second,1,bit2);update(p.second,p.first,bit1);}cout<<ans<<endl;}signed main(){IOS#ifndef ONLINE_JUDGEfreopen("IO\\in.txt","r",stdin);freopen("IO\\out.txt","w",stdout);#endifint tn=1;while(tn--){solve();}}