2023牛寒6--阿宁的二进制

阿宁有一个长度为n的数组a下标从1开始。
定义f(x)是x在二进制表示下1的个数。例如5的二进制是101因此f(5)=2。
阿宁有q次询问每次询问后数组恢复原样。
在一次询问中给出k。在一次操作中可以选择一个数i(1≤i≤n)将ai修改为f(ai)。请你恰好进行k次操作要求整个数组的最大值最小这个最大值是多少?

输入描述
第一行两个整数n,q。
第二行n个整数ai。
接下来q行每行一个整数k。
1≤n,q≤2×10^5
1≤ai,k≤10^9

输出描述

输出q行每行一个整数表示每次询问的答案。

输入

5 3
4 5 4 2 7
1
3
10

输出

5
4
1

说明

第一次询问将7修改为3数组变成[4,5,4,2,3]最大值是5。
第二次询问将5改为22改为17改为3数组变成[4,2,4,1,3]最大值是4。
第三次询问全都改为1数组变成[1,1,1,1,1]最大值是1。

解析首先得知道一个数经过f( )变为一个1的次数不会很大如果我们每次询问去操作就会超时了然后可以用优先队列预处理出第id次操作下最大值是多少存入map每次询问查询一下map即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
unordered_map<int,int> mp;
int f(int x) {//求二进制下1的个数
    int cnt=0;
    while(x){
        cnt++;
        x&=x-1;
    }
    return cnt;
}
priority_queue<int> q;
void solve()
{
	int n,Q;
	scanf("%d%d",&n,&Q);
	while(n--)
	{
		int x;
		scanf("%d",&x);
		q.push(x);
	}
	int id=0;//记录次数
	while(1)
	{
		int x=q.top();
		if(x==1) break;//如果当前最大值是1那么就直接退出就好
		q.pop();
		q.push(f(x));
		id++;
		mp[id]=q.top();//记录操作id次最大值
	}
	while(Q--)
	{
		int ask;
		scanf("%d",&ask);
		if(!mp[ask]) printf("1\n");//表示这么多操作下肯定全部数字都为1
		else printf("%d\n",mp[ask]); 
	}
}
int main()
{
	solve();
	return 0;
}