牛客练习赛96 (A - C）题解

牛客练习赛96比赛地址

A -- 小y的平面B -- 小y的树C -- 小y的序列

签到题，将所有的坐标按照左端点排序，然后遍历一遍查有没有纵坐标递减的情况，如果没有答案为YES, 有答案为NO （这题数据应该是出水了，不用排序也能过）

#include 
#include 
#include 
#include 
#include 
 
using namespace std;
 
typedef long long ll;
 
const int N = 1e6 + 10;
 
struct Node{
    int x, y;
}a[N];
 
bool cmp(Node u, Node v)
{
    if(u.x != v.x) return u.x < v.x;
    else return u.y < v.y;
}
 
int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++ ){
        cin >> a[i].x >> a[i].y;
    }
     
    sort (a + 1, a + 1 + n, cmp);
     
    for (int i = 1; i < n; i ++ ){
        if(a[i].y > a[i + 1].y){
            cout << "NO" << endl;
            return 0;
        }
    }
     
    cout << "YES" << endl;
}

最容易想到的应该是按层枚举每层提供的权值，但是这样太复杂了。这里提供一种更简单的方法 – 计算每条边经过的次数，即位答案。

用最简单的四层满二叉树来举例子：
要计算一条边的经过次数， 即为 该边以下所有节点的个数 * 除了该边以下的所有节点的个数

例如 ：
第二层所有边经过次数 = 7 * 8 * 2 = 112
第三层所有边经过次数 = 12 * 3 * 4 = 144
第四层所有边经过次数 = 1 * 14 * 8 = 112

用sum数组记录一个前缀和 表示前i层所有节点的个数
用cnt数组记录每一层的节点个数

而我们可以观察到 第i层的边以下所有的点就等于sum[n - i + 1]
所以每一层所有边提供的权值为 : cnt[i] * (sum[n] - sum[n - i + 1]) * sum[n - i + 1]

#include 
#include 

using namespace std;

typedef long long ll;

const int N = 1e6 + 10, mod = 1e9 + 7;
ll cnt[N] ,sum[N];

int main()
{
	int n, k;
	cin >> n >> k;
	cnt[1] = 1, sum[1] = 1;
	for (int i = 2; i <= n; i ++ ){
		cnt[i] = (cnt[i - 1] * k) % mod;
		sum[i] = (sum[i - 1] + cnt[i]) % mod;
	}
	
	long long ans = 0;
	for (int i = 2; i <= n; i ++ ){
		ans += cnt[i] % mod * (sum[n] - sum[n - i + 1] + mod) % mod * sum[n - i + 1];
        ans %= mod;
	}
	
	cout << ans << endl;
}

一道RMQ二分查询的题目，将RMQ算法掌握之后这题就很简单

该题的一个性质:固定左端点后，右端点往后移，区间内最大值减最小值是单调递增的

我们遍历固定每个左端点 i，去查找从左端点开始， 二分查找最大值减最小值为k的右端点r，然后r - i就为区间个数

#include 
#include 
#include 
#include 

using namespace std;

const int N = 1e6 + 10;

int n, k;
int a[N];
int fx[N][30], fi[N][30];

void init()
{	
	for (int j = 1; j < 22; j ++ ){
		for (int i = 1; i + (1 << j) - 1 <= n; i ++ ){
			fx[i][j] = max(fx[i][j - 1], fx[i + (1 << (j - 1))][j - 1]);
			fi[i][j] = min(fi[i][j - 1], fi[i + (1 << (j - 1))][j - 1]);
		}
	}
}

int check(int l, int r)
{
	int p = log2(r - l + 1);
	int s = max(fx[l][p], fx[r - (1 << p) + 1][p]) - min(fi[l][p], fi[r - (1 << p) + 1][p]);
    return s;
}

int main()
{
	cin >> n >> k;
	for (int i = 1; i <= n; i ++ ){
		cin >> a[i];
		fx[i][0] = a[i], fi[i][0] = a[i];
	} 
	
    init();
    
	long long ans = 0;
	for (int i = 1; i <= n; i ++ ){
		int l = i, r = n;
		while (l < r){
			int mid = l + r >> 1;
			if(check(i, mid) < k) l = mid + 1;
			else r = mid;
		}
		
		int left = l;
		if(check(i, left) != k) continue;
		
		l = i, r = n;
		while (l < r){
			int mid = l + r + 1 >> 1;
			if(check(i, mid) <= k) l = mid;
			else r = mid - 1;
		}
		ans += l - left + 1;
	}
	
	cout << ans << endl;
}