Q1 卡片

问题描述

小蓝有 $k$ 种卡片, 一个班有 $n$ 位同学, 小蓝给每位同学发了两张卡片, 一 位同学的两张卡片可能是同一种, 也可能是不同种, 两张卡片没有顺序。没有 两位同学的卡片都是一样的。

给定 $n$, 请问小蓝的卡片至少有多少种?

输入格式

输入一行包含一个正整数表示 $n$ 。

输出格式

输出一行包含一个整数, 表示答案。

分析:题意也就是求一个最小的k使得1~k的数字出现的无序对(a, b)数量能大于等于n由排列组合这样产生的无序对数量最多是$k\ast (k+1)/2$可以通过二分来寻找这个最小的k.

/*
* @Author: gorsonpy
* @Date:   2023-01-16 13:12:41
* @Last Modified by:   gorsonpy
* @Last Modified time: 2023-01-16 13:27:22
*/
#include<iostream>
using namespace std;
using LL = long long;
int main()
{
    int n;
    cin >> n;

    int l = 1, r = 1e9;

    while(l < r)
    {
        int mid = l + r >> 1;
        if((LL)mid * (mid + 1) < 2 * n) l = mid + 1;
        else r = mid;
    }

    cout << r << endl;
    return 0;
}

Q2(暴力分第几小

问题描述

给定一个数组 A = ( a 1 , a 2 , ⋯ , a n ) A=\left(a_1, a_2, \cdots, a_n\right) A=(a1​,a2​,⋯,an​), 请对该数组执行 $m$ 次修改或查询操作: 若操作为 $1xy$, 表示将 a x a_x ax​ 的值修改为 $y$;

若操作为 $2lrp$ 表示求 a p a_p ap​ 在 a l , a l + 1 , ⋯ , a r a_l, a_{l+1}, \cdots, a_r al​,al+1​,⋯,ar​ 中是第几小的比 a p a_p ap​ 小的元 素个数加 1)。

输入格式

输入的第一行包含一个整数 $n$ 。

第二行包含 $n$ 个整数 a 1 , a 2 , ⋯ , a n a_1, a_2, \cdots, a_n a1​,a2​,⋯,an​, 表示数组中每个数的初始值, 相邻的 整数之间用一个空格分隔。

第三行包含一个整数 $m$ 。

接下来 $m$ 行每行包含一个操作, 可能是 1 x i y i 1 x_i y_i 1xi​yi​ 或 2 l i r i p i 2 l_i r_i p_i 2li​ri​pi​, 相邻的整数之 间用一个空格分隔。

输出格式

输出一行, 包含多个整数, 相邻的整数之间用一个空格分隔, 依次表示第 二种操作的答案。

/*
* @Author: gorsonpy
* @Date:   2023-01-16 13:40:36
* @Last Modified by:   gorsonpy
* @Last Modified time: 2023-01-16 13:45:47
*/
#include<iostream>
using namespace std;

const int N = 1e5 + 10;
int a[N];

int cal(int l, int r, int x)
{
	int cnt = 0;
	for(int i = l; i <= r; ++i)
		if(a[i] < x) ++cnt;
	return cnt + 1;
}
int main()
{
	int n;
	cin >> n;
	for(int i = 1; i <= n; ++i) cin >> a[i];
	int m;
	cin >> m;

	while(m--)
	{
		int op, x, y, z;
		cin >> op >> x >> y;
		if(op == 1) a[x] = y;
		else
		{
			cin >> z;
			cout << cal(x, y, a[z]) << " ";
		}
	}

	return 0;
}