求助!树状数组+二分,二分边界L=1时为何会T?
查看原帖
求助!树状数组+二分,二分边界L=1时为何会T?
723548
Li15320556637楼主2022/6/17 17:08

二分边界L=1时#3会T 改成L=0就过了 ,, 为什么呢

#include<bits/stdc++.h>
#define int long long
using namespace std;
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<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
inline void write(int x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9){
		write(x/10);
	}
	putchar(x%10+'0');
}
int n;
struct fg{
	int id,z;
};
struct bit{
	int t[500005];
	int lowbit(int x){
		return x&(-x);
	}
	void change(int k,int x){
		while(k<=2e5){
			t[k]+=x;
			k+=lowbit(k);
		}
	}
	int query(int k){
		int ans=0;
		while(k>0){
			ans+=t[k];
			k-=lowbit(k);
		}
		return ans;
	}
}t1;
int ri[200005];
signed main()
{
	n=read();int ans=0;
	while(n--){
		char s;
		cin>>s;
		int an=0;
		if(s=='A'){
			int a=read(),b=read();
			while(1){
				int l=1,r=b;//问题在这
				while(l<r){
					int mid=l+r>>1;
					if(t1.query(mid)<t1.query(r)){
						l=mid+1;
					}
					else {
						r=mid;
					}
				}
				if(ri[r]>=a){
					ans--;
					an++;
					t1.change(r,-1);
				}
				else break;
			}
			write(an);
			putchar('\n');
			t1.change(a,1);
			ri[a]=b;
			ans++;
		}
		else {
			write(ans);
			putchar('\n');
		}
	}
    return 0;
}
2022/6/17 17:08
加载中...