A sequence a=[a1,a2,…,al]a=[a1,a2,…,al] of length ll has an ascent if there exists a pair of indices (i,j)(i,j) such that 1≤i<j≤l1≤i<j≤l and ai<ajai<aj. For example, the sequence [0,2,0,2,0][0,2,0,2,0] has an ascent because of the pair (1,4)(1,4), but the sequence [4,3,3,3,1][4,3,3,3,1] doesn’t have an ascent.

Let’s call a concatenation of sequences pp and qq the sequence that is obtained by writing down sequences pp and qq one right after another without changing the order. For example, the concatenation of the [0,2,0,2,0][0,2,0,2,0] and [4,3,3,3,1][4,3,3,3,1] is the sequence [0,2,0,2,0,4,3,3,3,1][0,2,0,2,0,4,3,3,3,1]. The concatenation of sequences pp and qq is denoted as p+qp+q.

Gyeonggeun thinks that sequences with ascents bring luck. Therefore, he wants to make many such sequences for the new year. Gyeonggeun has nn sequences s1,s2,…,sns1,s2,…,sn which may have different lengths.

Gyeonggeun will consider all n2n2 pairs of sequences sxsx and sysy (1≤x,y≤n1≤x,y≤n), and will check if its concatenation sx+sysx+sy has an ascent. Note that he may select the same sequence twice, and the order of selection matters.

Please count the number of pairs (x,yx,y) of sequences s1,s2,…,sns1,s2,…,sn whose concatenation sx+sysx+sy contains an ascent.

Input
The first line contains the number nn (1≤n≤1000001≤n≤100000) denoting the number of sequences.

The next nn lines contain the number lili (1≤li1≤li) denoting the length of sisi, followed by lili integers si,1,si,2,…,si,lisi,1,si,2,…,si,li (0≤si,j≤1060≤si,j≤106) denoting the sequence sisi.

It is guaranteed that the sum of all lili does not exceed 100000100000.

Output
Print a single integer, the number of pairs of sequences whose concatenation has an ascent.

Examples
Input
5
1 1
1 1
1 2
1 4
1 3
Output
9
Input
3
4 2 0 2 0
6 9 9 8 8 7 7
1 6
Output
7
Input
10
3 62 24 39
1 17
1 99
1 60
1 64
1 30
2 79 29
2 20 73
2 85 37
1 100
Output
72
Note
For the first example, the following 99 arrays have an ascent: [1,2],[1,2],[1,3],[1,3],[1,4],[1,4],[2,3],[2,4],[3,4][1,2],[1,2],[1,3],[1,3],[1,4],[1,4],[2,3],[2,4],[3,4]. Arrays with the same contents are counted as their occurences.
題意：給定n個數組，按照數組加法那樣把任意兩個數組拼接到一起。如果有1≤i<j≤l且ai <aj這樣的，就是一個題目要求的連接串，也可以自己和自己連接。問一共可以有多少個連接串。
思路：如果數組本身就是這樣的連接串，那么它和任意一個數組都可以組成題目要求的連接串。如果數組ai不是題目中的連接串，并且這個數組的最大值比其余數組aj的最小值還要小的話，這樣就不能組成連接串了（ai+aj不行，但是aj+ai可以）。那么我們可以把所有的不是題目要求的連接串中的最大值最小值求出來，然后對最小值數組排序，之后把最大值數組去最小值數組中二分，找出不符合的，最后用n*n減去就行。
代碼如下：

#include<bits/stdc++.h> #define ll long long using namespace std;const int maxx=1e5+100; vector<int> p[maxx]; int l[maxx],r[maxx],vis[maxx]; int n;int main() {scanf("%d",&n);int x,y;for(int i=1;i<=n;i++){scanf("%d",&x);for(int j=0;j<x;j++){scanf("%d",&y);p[i].push_back(y);}}memset(vis,0,sizeof(vis));for(int i=1;i<=n;i++){for(int j=0;j<p[i].size();j++){for(int k=j+1;k<p[i].size();k++){if(p[i][j]<p[i][k]){vis[i]=1;break;}}if(vis[i]) break;}}int cnt=0;for(int i=1;i<=n;i++){if(!vis[i]){sort(p[i].begin(),p[i].end());l[++cnt]=p[i][0],r[cnt]=p[i][p[i].size()-1];}}ll num=0;sort(l+1,l+1+cnt);for(int i=1;i<=cnt;i++){int pos=lower_bound(l+1,l+1+cnt,r[i])-l-1;num+=cnt-pos;}cout<<((ll)n*(ll)n)-num<<endl;//注意用long long }

努力加油a啊，(^o)/~

總結

以上是生活随笔為你收集整理的New Year and Ascent Sequence（二分）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。