题目描述
Problem Statement
The season for Snuke Festival has come again this year. First of all, Ringo will perform a ritual to summon Snuke. For the ritual, he needs an altar, which consists of three parts, one in each of the three categories: upper, middle and lower.
He has N parts for each of the three categories. The size of the i-th upper part is Ai, the size of the i-th middle part is Bi, and the size of the i-th lower part is Ci.
To build an altar, the size of the middle part must be strictly greater than that of the upper part, and the size of the lower part must be strictly greater than that of the middle part. On the other hand, any three parts that satisfy these conditions can be combined to form an altar.
How many different altars can Ringo build? Here, two altars are considered different when at least one of the three parts used is different.
Constraints
- 1≤N≤10^5
- 1≤Ai≤10^9(1≤i≤N)
- 1≤Bi≤10^9(1≤i≤N)
- 1≤Ci≤10^9(1≤i≤N)
- All input values are integers.
这道题我当时比赛的时候，因为前两题都很水，但这道题画风明显和前两题不是一个档次，大概起码是提高了一个档次以上，（但大概在大佬眼里还是道水题吧）。
这道题n^3的做法应该是比较简单的，然后我就想了想，搞了个O（nlogn）的方法。
需要详细题解的在下面发评论我再发，先放一下我的代码。
#include#include #include using namespace std;long long n,f[100001][5],l=0,r,mid,a[1000001],b[100001],c[100001];int main(){ scanf("%lld",&n); for(int j=1;j<=n;++j) scanf("%lld",&a[j]); for(int j=1;j<=n;++j) scanf("%lld",&b[j]); for(int j=1;j<=n;++j) scanf("%lld",&c[j]); sort(a+1,a+1+n);sort(b+1,b+1+n);sort(c+1,c+1+n); for(int i=1;i<=n;++i) { f[i][1]=i; } for(int j=1;j<=n;++j) { l=1,r=n; while(l<=r) { mid=(l+r)/2; if(b[j]<=a[mid]) { r=mid-1; } else l=mid+1; } f[j][2]=f[j-1][2]+f[r][1]; } for(int j=1;j<=n;++j) { l=1,r=n; while(l<=r) { mid=(l+r)/2; if(c[j]<=b[mid]) { r=mid-1; } else l=mid+1; } f[j][3]=f[j-1][3]+f[r][2]; } printf("%lld",f[n][3]); return 0;}
