zkw线段树做法,何处思路错误?
查看原帖
zkw线段树做法,何处思路错误?
799098
chengzihan620楼主2024/3/28 19:26
#include<bits/stdc++.h>
using namespace std;
const int maxn=100010;
int tree1[maxn*3],tree2[maxn*3];
int n,m,N=1; 
void update(int l,int r){
	for(l+=N;l;l>>=1)tree1[l]++;
	for(r+=N;r;r>>=1)tree2[r]++;
}
int query(int l,int r){
	int ans1=0,ans2=0,i;
	for(i=N,l+=N+1;l^i^1;l>>=1,i>>=1){
		if(~i&1)ans1+=tree2[i^1];
		if(l&1)ans1+=tree2[l^1];
	}
	for(i=N,r+=N+1;r^i^1;r>>=1,i>>=1){
		if(~i&1)ans2+=tree1[i^1];
		if(r&1)ans2+=tree1[r^1];
	}
	return ans2-ans1;
}
signed main(){
	cin>>n>>m;
	while(N<=n+1)N<<=1;
	for(int i=1;i<=m;i++){
		int op,x,y;
		cin>>op>>x>>y;
		if(op==1)update(x,y);
		if(op==2)cout<<query(x,y)<<endl;
	}
	return 0;
}
2024/3/28 19:26
加载中...