简单树状数组板子,10 分萌新求教
查看原帖
简单树状数组板子,10 分萌新求教
754021
fish_love_cat楼主2023/7/12 13:24

按照第一篇题解敲得,思路也是学的题解,只有十分,错了十几发,要 emo 了/kk

#include<bits/stdc++.h>
using namespace std;
#define int long long
int xsxqz(int a,int b){//向上/下取整
    int c=a/b;
    if(b*c!=a){
        if(a<0) c++;
        else c--;
    }
    return c;
}
bool sc[1000005];//删除
int dy[20000005],xy[20000005],zl[1000005],sx[1000005];//大于,小于,种类,所需
int top,hcl;//长度,恒成立
int lowbit(int x){return x&(-x);}//lowbit
void add(int a,int b,int sz[]){
    a+=1000100;
    for(;a<=2000100;a+=lowbit(a)) sz[a]+=b;
}//增加
int qh(int a,int sz[]){//求和
    int sum=0;a+=1000000;
    for(;a;a-=lowbit(a)) sum+=sz[a];
    return sum;
}
signed main(){
    int t;
    cin>>t;
    while(t--){
        string s;
		cin>>s;
        if(s[0]=='A'){//增加
            int a,b,c;
            cin>>a>>b>>c;
            if(a==0){
                if(b>c) hcl++,zl[++top]=3;
                else zl[++top]=0;
            }
            if(a>0){
                sx[++top]=xsxqz((c-b)*1.0,a);
                zl[top]=1;
                if(sx[top]>1000000) zl[top]=0;
                else if(sx[top]<-1000000) zl[top]=3,hcl++;
                else add(sx[top],1,dy);
            }
            if(a<0){
                sx[++top]=xsxqz((c-b),a);
                zl[top]=2;
                if(sx[top]<-1000000) zl[top]=0;
                else if(sx[top]>1000000) zl[top]=3,hcl++;
                else add(sx[top],1,xy);
            }
        }
        if(s[0]=='D'){//删除
            int ii;
            cin>>ii;
            if(!sc[ii]){
                sc[ii]=true;
                if(zl[ii]==1) add(sx[ii],-1,dy);
                if(zl[ii]==2) add(sx[ii],-1,xy);
                if(zl[ii]==3) hcl--;
            }
        }
        if(s[0]=='Q'){//求和
            int k;
            cin>>k;
            cout<<hcl+qh(k-1,dy)+qh(1000000,xy)-qh(k,xy)<<endl;
        }
    }
    return 0;
}

样例能过,不知错哪了。

悬一关。

2023/7/12 13:24
加载中...