萌新刚学OI,手写 BIT 30pts求助

回复帖子

@云浅知处 2020-11-22 00:14 回复

qwq

只过了 #2,3,9

其他输出我看了几个,大概都是大部分相同,有一些地方会差 $1$。。

不想用平衡树的原因是因为怕调一天,这个起码好调点(

#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<cmath>

#define MAXN 1000001
#define MAXM 2000001
#define lowbit(x) ((x)&(-(x)))

using namespace std;

int r,n,t[MAXN],l[MAXN];
//r:恒成立的不等式数量
//t[]:用于记录每一个 (c-b)/a
//l[]:用于记录每个不等式的性质
//l[id]=0 表示不等式方向为 >
//l[id]=1 表示不等式方向为 <
//l[id]=23333333 表示不等式恒成立
//l[id]=-23333333 表示不等式恒不成立
bool del[MAXN];//del[]:是否已经删除

struct BIT{

    int c[MAXN<<2];

    inline void PreFix(){
        memset(c,0,sizeof(c));
    }

    inline void modify(int x,int v){
        x+=MAXN;
        for(int i=x;i<=MAXM;i+=lowbit(i)){
            c[i]+=v;
        }
    }

    inline int query(int x){
        x+=MAXN;
        int ans=0;
        for(int i=x;i;i-=lowbit(i)){
            ans+=c[i];
        }
        return ans;
    }

};//树状数组

BIT tree1,tree2;

int cnt=0;

void donothing(){
    //珂朵莉珂爱!珂朵莉珂爱!珂朵莉珂爱!珂朵莉珂爱!珂朵莉珂爱!珂朵莉珂爱!珂朵莉珂爱!珂朵莉珂爱!珂朵莉珂爱!珂朵莉珂爱!珂朵莉珂爱!珂朵莉珂爱!珂朵莉珂爱!珂朵莉珂爱!珂朵莉珂爱!珂朵莉珂爱!
    //铃酱 txdy!铃酱 txdy!铃酱 txdy!铃酱 txdy!铃酱 txdy!铃酱 txdy!铃酱 txdy!铃酱 txdy!铃酱 txdy!铃酱 txdy!铃酱 txdy!铃酱 txdy!铃酱 txdy!铃酱 txdy!铃酱 txdy!铃酱 txdy!
    //『君指先跃动の光は、私の一生不変の信仰に、唯私のお姉さま永生き!』
}

#define qwq 23333333
#define awa 1000000

//由于不知道为啥我感觉<cmath>里面的上下取整炸了,所以自己写了一个。
//看着自己丑陋的代码,顿时感觉调代码的时候什么迷惑行为都能干出来(捂脸
//为了防止负数取模出神必错误,专门全用 abs() 转成了正数进行运算,最后判断正负qwq
//其实正常写应该是没问题的,只是调代码的时候抱着「试一试吧」的心态改了一下qwq

int cceeiill(int aa,int bb){
    int pd=aa/bb;
    int aaa=abs(aa);
    int bbb=abs(bb);
    int f=1;
    if(pd<0)f=-1;
    if(aaa%bbb==0)return f*(aaa/bbb);
    else{
        int ccc=aaa%bbb;
        aaa-=ccc;
        return f*(aaa/bbb)+1;
    }
}

int fflloorr(int aa,int bb){
    int pd=aa/bb;
    int aaa=abs(aa);
    int bbb=abs(bb);
    int f=1;
    if(pd<0)f=-1;
    if(aaa%bbb==0)return f*(aaa/bbb);
    else{
        int ccc=aaa%bbb;
        aaa-=ccc;
        return f*(aaa/bbb);
    }
}

int main(void){

    //freopen("P5482_1.in","r",stdin);
    //freopen("P5482out.out","w",stdout);

    scanf("%d",&n);

    for(int i=1;i<=n;i++){
        char opt[8];
        scanf("%s",opt);
        if(opt[0]=='A'){
            ++cnt;
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            //分类讨论,上面已经说过。
            if(a==0){
                if(b>c){
                    r++;
                    l[cnt]=qwq;
                }
                else l[cnt]=-qwq;
            }
            else if(a>0){
                int p=fflloorr((c-b),a);
                //printf("\n%d\n",p);
                l[cnt]=0;
                t[cnt]=p;
                if(p< -awa){
                    r++;
                    l[cnt]=qwq;
                }
                else if(p>awa)l[cnt]=-qwq;
                else{
                    tree1.modify(p,1);
                }
            }
            else{
                int p=cceeiill((c-b),a);
                l[cnt]=1;
                t[cnt]=p;
                if(p< -awa)l[cnt]=-qwq;
                else if(p>awa){
                    l[cnt]=qwq;
                    r++;
                }
                else{
                    tree2.modify(p,1);
                }
            }
        }
        else if(opt[0]=='D'){
            int id;
            scanf("%d",&id);
            if(del[id])continue;
            del[id]=1;
            if(l[id]==qwq)r--;
            else if(l[id]==-qwq)donothing();
            else if(l[id]==0)tree1.modify(t[id],-1);
            else if(l[id]==1)tree2.modify(t[id],-1);
        }
        else{
            int k;
            scanf("%d",&k);
            printf("%d\n",r+tree1.query(k-1)+tree2.query(awa)-tree2.query(k));
        }
    }

    return 0;
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。