Submission #76054668

---

Source Code Expand

#include <bits/stdc++.h>
#define int long long
#define ll long long
#define ull unsigned long long
#define inf 4e18
#define eps 1e-9
#define il inline
#define ls 2*k
#define rs 2*k+1
using namespace std;
const int N=1e6+5,M=250005;
const int mod=998244353;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*f;
}
int n,q,a[N];
struct BIT{
    int f[N];
    inline void add(int p,int v){
        for(;p<=1e6;p+=(p&-p)) f[p]+=v;
        return ;
    }
    inline int query(int p){
        int res=0;
        for(;p;p-=(p&-p)) res+=f[p];
        return res;
    }
}tr;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int tc=1;
	while(tc--){
		cin>>n>>q; 
		int now=1;
		tr.add(1,n);
		for(int i=1;i<=n;i++) a[i]=1;
		while(q--){
			int op,x;
			cin>>op>>x;
			if(op==1){
				tr.add(a[x],-1);
				a[x]++;
				tr.add(a[x],1);
				if(tr.query(now)==0) now++;
//				cout<<x<<' '<<a[x]<<'\n';
			}
			else{
				x+=now;
				cout<<(tr.query(1e6)-tr.query(x-1))<<'\n';
//				cout<<x<<"---\n";
			}
		}
	}
	return 0;
}
/*
input： 
1
3 4 1
1 2 3
3 3 4 7 
6
output：
14

从大到小按位考虑，则如果能在不会让前面取不到的情况下取到，那么一定要操作。 
*/

Submission Info

Judge Result