本文主要是介绍Codeforces Round #261 (Div. 2) D，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
D. Pashmak and Parmida's problem
题意：n个整数a1~an。1<=i<j<=n，问有多少组i，j满足这样的情况：a1~ai中值为ai的数的个数大于aj~an中值为aj的数的个数。。是不是有点绕。。
思路：树状数组。为了做这题，恶补了一下线段树，树状数组，逆序数对的知识。。虽然搞了好久，也算值了。先统计f(1, i, ai) 的值，存入一个数组并维护树状数组。然后逆序扫描，计算f(j, n, aj)的同时反向维护树状数组，说得形象点就是让树状数组存的内容不断“撤销”，以获得它先前的值。这样就可以统计出j取每一个值时（枚举j，而i由树状数组维护不用枚举），f(1, i, ai) 大于f(j, n, aj)有多少组，加起来就是答案。这样一来总的复杂度降为了O(nlogn)！
#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <cstdlib>
#include <string>
#include <memory.h>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <ctype.h>
#define INF 10000000
#define ll long long
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define MAXN 100010using namespace std; int n;
int a[1000010];
int b[1000010];
int c[1000010];
map<int,int> mp;inline int lowbit(int x){return x&(x^(x-1));
}inline void update(int pos,int num){while(pos<=n){c[pos]+=num;pos+=lowbit(pos);}
}inline int sum(int end){int re=0;while(end){re+=c[end];end-=lowbit(end);}return re;
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);while(cin>>n){memset(c,0,sizeof(c));mp.clear();for(int i=1;i<=n;i++){cin>>a[i];mp[a[i]]++;b[i]=mp[a[i]];update(b[i],1);}mp.clear();ll ans=0;for(int i=n;i>=1;i--){mp[a[i]]++;update(b[i],-1);ans+=(i-1-sum(mp[a[i]]) ); }cout<<ans<<endl;}return 0;
}这篇关于Codeforces Round #261 (Div. 2) D的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
