求调
查看原帖
求调
1120256
Mini_Creation楼主2024/11/22 19:07
#include<bits/stdc++.h>
#define lc u<<1
#define rc u<<1|1
const int N=500005;
#define int long long
using namespace std;
int n,m;
struct tree{
	int l,r,sum[2];
}tr[4*N];
void pushup(int u,int k){
	tr[u].sum[k]=tr[lc].sum[k]+tr[rc].sum[k];
}
void build(int u,int l,int r){
	tr[u].l=l;
	tr[u].r=r;
	if(l==r)return;
	int mid=(l+r)>>1;
	build(lc,l,mid);
	build(rc,mid+1,r);
}
int query(int u,int x,int y,int k){
	if(x>tr[u].r||y<tr[u].l)return 0;
	if(x<=tr[u].l&&tr[u].r<=y) return tr[u].sum[k];
	return query(lc,x,y,k)+query(rc,x,y,k);
}
void change(int u,int x,int k){
	if(tr[u].l==tr[u].r){
		tr[u].sum[k]++;
		return ;
	}
	if(x<=tr[lc].r)change(lc,x,k);
	else change(rc,x,k);
	pushup(u,k); 
}
signed main(){
	cin>>n>>m;
	build(1,1,n);
	for(int i=1;i<=m;i++){
		int q,l,r;
		cin>>q>>l>>r;
		if(q==1) change(1,1,0),change(1,r,1);
		else cout<<query(1,1,r,0)-query(1,1,l-1,1)<<endl;
	}
	return 0;
}
2024/11/22 19:07
加载中...