首页 > 代码库 > 【vijos】1768 顺序对的值（特殊的技巧）
【vijos】1768 顺序对的值（特殊的技巧）
https://vijos.org/p/1768
之前不知道为什么，我yy了一个n^2的做法，但是没能写出来。。sad
然后看了题解才发现这题好神。。
为什么一定要照着题意找两个点然后算呢？这就是问题所在。。。
我们可以观察每一个点，发现他的贡献恰好是左边比他小的数和右边比他大的数组成的顺序对，那么一共有l*r对，所以答案就加上l*r
这种题的思想很好啊。。以后做这些题可以用个体来想整体，orz
（还有这题他们说lgn使用树状数组维护l和r，怎么维护啊QAQ
#include <cstdio>#include <cstring>#include <cmath>#include <string>#include <iostream>#include <algorithm>#include <queue>using namespace std;#define rep(i, n) for(int i=0; i<(n); ++i)#define for1(i,a,n) for(int i=(a);i<=(n);++i)#define for2(i,a,n) for(int i=(a);i<(n);++i)#define for3(i,a,n) for(int i=(a);i>=(n);--i)#define for4(i,a,n) for(int i=(a);i>(n);--i)#define CC(i,a) memset(i,a,sizeof(i))#define read(a) a=getint()#define print(a) printf("%d", a)#define dbg(x) cout << (#x) << " = " << (x) << endl#define printarr2(a, b, c) for1(_, 1, b) { for1(__, 1, c) cout << a[_][__]; cout << endl; }#define printarr1(a, b) for1(_, 1, b) cout << a[_] << ‘\t‘; cout << endlinline const int getint() { int r=0, k=1; char c=getchar(); for(; c<‘0‘||c>‘9‘; c=getchar()) if(c==‘-‘) k=-1; for(; c>=‘0‘&&c<=‘9‘; c=getchar()) r=r*10+c-‘0‘; return k*r; }inline const int max(const int &a, const int &b) { return a>b?a:b; }inline const int min(const int &a, const int &b) { return a<b?a:b; }const int N=5005;typedef long long ll;int a[N], n;ll ans;int main() { read(n); for1(i, 1, n) read(a[i]); for1(i, 1, n) { ll l=0, r=0; for1(j, 1, i-1) if(a[j]<a[i]) ++l; for1(j, i+1, n) if(a[j]>a[i]) ++r; ans+=l*r; } printf("%lld\n", ans); return 0;}
描述
给定一个序列a，a中任意两个元素都不等。如果i<j,且 a[i]<a[j]，则我们称a[i],a[j]为一个顺序对，这个顺序对的值是指a[i+1],a[i+2]…….a[j-1]中比a[i]大， 且比a[j]小的数的个数。求一个序列中所有顺序对的值的和。
格式
输入格式
第一行一个数n，表示序列a中元素的个数。
第二行n个数，第i个数表示a[i]。
输出格式
输出一个数，序列a中所有顺序对的值的和。
样例1
样例输入1[复制]
51 5 3 4 2
样例输出1[复制]
1
限制
每个测试点2s。
提示
对于100%的数据，2<=n<=5000，a[i]<=10^9。
【vijos】1768 顺序对的值（特殊的技巧）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。