NC14522 珂朵莉的数列
珂朵莉的数列
https://ac.nowcoder.com/acm/problem/14522
题目描述:
给出一个序列,求序列中所有子区间中逆序对个数的和。
做法:
将每一个逆序对分开来看,假设存在···a【l】···a【r】···,且a【l】>a【r】,那么包含这个逆序对的区间就是左端点在1-l,右端点在r-n的任意一个区间,那么这样的区间一共是l*(n-r+1)个,考虑用树状数组解决,但是题目的数据较大,另外需要离散化,离散后对于a【i】,可以在树状数组中维护其左边界数量,右边界的数量则是(n-i+1)每次相乘累加即可,答案爆long long可以用__int128。
#include<iostream> #include<cstdio> #include<vector> #include<cmath> #include<string> #include<cstring> #include<algorithm> #include<queue> #include<map> #include<set> #define endl '\n' #define all(s) s.begin(),s.end() #define lowbit(x) (x&-x) #define rep(i,a,n) for (int i=a;i<=n;i++) #define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define mem(a,b) memset(a,b,sizeof(a)) #define fi first #define se second #define pb push_back #define pi acos(-1.0) using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; const int mod=1e9+7; const double eps=1e-8; const int inf=0x3f3f3f3f; const int N=1e6+10; ll a[N],bit[N]; vector<int>v; void add(int x,int k) { while(x<N){ bit[x]+=k; x+=lowbit(x); } } ll sum(int x) { ll ans=0; while(x>0){ ans+=bit[x]; x-=lowbit(x); } return ans; } int getid(int x) { return lower_bound(all(v),x)-v.begin()+1; } void print(__int128 x){ if(x<0){ putchar('-'); x=-x; } if(x>9) print(x/10); putchar(x%10+'0'); } int main() { ll n; cin>>n; for(int i=1;i<=n;i++) cin>>a[i],v.pb(a[i]); sort(all(v)); v.erase(unique(all(v)),v.end()); __int128 ans=0; for(ll i=1;i<=n;i++){ int now=getid(a[i]); ans+=ll(sum(N-1)-sum(now))*(n-i+1); add(now,i); } print(ans); }