CF# 576 div2 C D

C题

题目 挺难理解的
新知识

long long maxx = 1LL << min((K * 8 / N), 31);

AC 代码

//MADE BY Y_is_sunshine;
//#include <bits/stdc++.h>
//#include <memory.h>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <cstdio>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <math.h>
 
#define INF 0x3f3f3f3f
#define MAXN 400005
#define maxn 105
 
const int mod = 1e9 + 7;
 
using namespace std;
 
int a[MAXN];
long long sum[MAXN];
int cnt;
 
int main()
{
// freopen("data.txt", "r", stdin);
 
	int N, K;
	cin >> N >> K;
 
	for (int i = 0; i < N; i++)
		scanf("%d", &a[i]);
 
	sort(a, a + N);
	int temp;
	for (int i = 0; i < N; i += temp) {
		cnt++;
		temp = 1;
		while (a[i] == a[i + temp]&&i+temp<N)
			temp++;
		sum[cnt] = sum[cnt-1] + temp;
	}
	
	long long maxx = 1LL << min((K * 8 / N), 31);
 
	long long ans = 0;
	long long i = 1, j = maxx;
	if (j >= cnt)
		ans = N;
	else {
		for (; j <= cnt; j++, i++)
			ans = max(ans, sum[j] - sum[i - 1]);
	}
	cout << N - ans << endl;
 
 
	//freopen("CON", "r", stdin);
	//system("pause");
	return 0;
}

D题
新知识： 优化 优化 优化 对于操作2 离线

//MADE BY Y_is_sunshine;
//#include <bits/stdc++.h>
//#include <memory.h>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <cstdio>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <math.h>
 
#define INF 0x3f3f3f3f
#define MAXN 100005
#define maxn 105
 
const int mod = 1e9 + 7;
 
using namespace std;
 
int a[MAXN << 1];
int b[MAXN << 1];
int c[MAXN << 1];
 
int main()
{
// freopen("data.txt", "r", stdin);
 
	int N;
	cin >> N;
	for (int i = 1; i <= N; i++)
		scanf("%d", &a[i]);
	int T;
	cin >> T;
	for (int i = 1; i <= T; i++) {
		int O;
		scanf("%d", &O);
		if (O == 1) {
			int x, y;
			scanf("%d%d", &x, &y);
			a[x] = y;
			b[x] = i;
		}
		else {
			scanf("%d", &c[i]);
		}
	}
 
	for (int i = T; i > 0; i--) {
		c[i] = max(c[i], c[i + 1]);
	}
 
	for (int i = 1; i <= N; i++)
		printf("%d ", max(a[i], c[b[i] + 1]));
 
 
// freopen("CON", "r", stdin);
// system("pause");
	return 0;
}