Codeforces：B. New Year and Ascent Sequence[模拟]

题面

A sequence a=[a1,a2,…,al] of length l has an ascent if there exists a pair of indices (i,j) such that 1≤i<j≤l and ai<aj. For example, the sequence [0,2,0,2,0] has an ascent because of the pair (1,4), but the sequence [4,3,3,3,1] doesn't have an ascent.
Let's call a concatenation of sequences p and q the sequence that is obtained by writing down sequences p and q one right after another without changing the order. For example, the concatenation of the [0,2,0,2,0] and [4,3,3,3,1] is the sequence [0,2,0,2,0,4,3,3,3,1]. The concatenation of sequences p and q is denoted as p+q.
Gyeonggeun thinks that sequences with ascents bring luck. Therefore, he wants to make many such sequences for the new year. Gyeonggeun has n sequences s1,s2,…,sn which may have different lengths.
Gyeonggeun will consider all n2 pairs of sequences sx and sy (1≤x,y≤n), and will check if its concatenation sx+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,y) of sequences s1,s2,…,sn whose concatenation sx+sy contains an ascent.
Input
The first line contains the number n (1≤n≤100000) denoting the number of sequences.
The next n lines contain the number li (1≤li) denoting the length of si, followed by li integers si,1,si,2,…,si,li (0≤si,j≤106) denoting the sequence si.
It is guaranteed that the sum of all li does not exceed 100000.
Output
Print a single integer, the number of pairs of sequences whose concatenation has an ascent.

题意

给定n个数列，统计其中任意两个数列组成的长数列中满足其中存在升序子列的长数列个数。

分析

答案统计分两种
第一种是某个数列自身满足存在升序子列，则与其搭配的任意数列都满足条件
第二种是两个数列都不存在升序子列，但是组合后存在
其中存在的条件是第一个数列的最小值小于第二个数列的最大值（即有升序子列）

合起来，对于某一个数列，只需统计其他数列中最小值小于该数列最大值的数列的个数即可

代码

#include <iostream>
#include <cstdio>
using namespace std;
inline int read() {
	register int x = 0, f = 1;
	register char c = getchar();
	while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0',c = getchar();
	return x * f;
}
const int MAXN = 1e6 + 1;
int n, l;
int maxs[MAXN], pre[MAXN], mins;
bool flag;
void init() {
	n = read();
	for (int i(1); i <= n; i++){
		l = read();
		mins = MAXN;
		flag = false;
		for (int j(1); j <= l; j++){
			int now = read();
			if (now > mins) flag = true;//如果满足自身存在升序子列，打标记
			maxs[i] = max(maxs[i], now);
			mins = min(mins, now);
		}
		if (flag){
			maxs[i] = 1e6;//
			mins = -1;
		}
		pre[mins + 1]++;//pre[i]记录小于i的数列最小值的个数
	}
	for (int i(1); i <= 1e6; i++){
		pre[i] += pre[i - 1];//记录前缀和
	}
}

void doit() {
	long long ans = 0;
	for (int i(1); i <= n; i++)
		ans += pre[maxs[i]];//统计最小值小于该数列最大值的数列个数
	printf("%lld\n", ans);
}

int main() {
	init();
	doit();
	return 0;
}