给定一个长度为N的数组A=[A1, A2, ... AN]，已知其中每个元素Ai的值都只可能是1, 2或者3。
请求出有多少下标三元组(i, j, k)满足1 ≤ i < j < k ≤ N且Ai < Aj < Ak。
第一行包含一个整数N
第二行包含N个整数A1, A2, ... AN。(1 ≤ Ai ≤ 3)
对于30%的数据，1 ≤ N ≤ 100
对于80%的数据，1 ≤ N ≤ 1000
对于100%的数据，1 ≤ N ≤ 100000
一个整数表示答案
6 1 3 2 1 2 3
3
思路：前缀和思路搞一搞
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+10; int a[N]; int main(){ int n; cin>>n; for(int i=1;i<=n;i++){ scanf("%d",&a[i]); } ll s3=0,s=0,sum=0;; for(int i=n;i>=1;i--){ if(a[i]==3){ s3++; } else if(a[i]==2){ s+=s3; } else if(a[i]==1){ sum+=s; } } cout<<sum<<endl; }
原文：http://www.cnblogs.com/hhxj/p/7357976.html