分类讨论大丈夫！！！WTF！！！

题意：

1.给你不等式ax>b

2.删除第i条插入的不等式

3.询问x=k时，满足多少个给定的不等式。

n的范围10w，k的绝对值范围是100w。

那么我们可以先解出这个不等式，把符合这个不等式的所有数所在的位置加一。

比如解出来x>1，就把2~100w全都加一。x<1，就把-100w~0全都加一。

那么明显就是修改区间，单点询问。可以用线段树很好的完成。

但是不知道为什么看到100w就后怕写线段树要玩常数。于是选择了树状数组。

用树状数组的话就需要差分。比如[l,r]都加一，那么在l的位置上加一，r+1的位置上减一。这个很基础。

负数的话下标怎么办呢？设置一个偏移量d=100w+1。修改第x个时，在第x+d个位置上修改。保证下标都是正的方便操作。

看来这道题已经没什么问题了。那我们去写写看？好的。

【以下为吐槽，看tips请跳过若干个自然段】

【四天前】树状数组两行秒。ax>b自以为是的除一除就算解好了。样例很快就过了。很自信的交上去。RE还是WA来着。。然后手忙脚乱改一改还是WA。。这个时候想到了对拍。网上搞了个标程拍一拍。。不拍不知道一拍吓一跳。。然后我就被拍扁重建了。（这是替罪羊树？

发现我解ax>b的方法很不科学。感觉都没考虑全。后来直接去玩double。结果精度萎出翔。。

然后我cave in了。。

【今天】上课的时候我重新想了想ax>b该怎么解。考虑a、b的正负，发现四种情况都列出来。四个if即可。最前面再特判一下a=0就没问题了。回来信心满满的写。

造了组大数据对拍过了。很高心。结果还是WA。真是要吐血。后来突然想到，万一它要删除已经删除掉的呢。那我不就挂了吗。于是我再开了个数组记录。这回，过了。。。。。

【吐槽完了】

几个tips：

1.a=0要特判

2.ax>b分四种情况讨论（我是这么做的保险，或者有更神的方法，可惜我不会

3.如果x解出来不在-100w~100w之间要特判

4.删除已经删除的不等式直接continue！！！

贴代码。本人放个r1的代码攒rp好了~

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int d=1000001,n=2000001,r=1000000;
int bit[n+3],A[100005],B[100005],del[100005]={0};
char op,buf[5000000],*p=buf,*o=buf;
inline void upd(int x,int d){ for(;x<=n;x+=x&-x) bit[x]+=d;}
inline int qry(int x){ int s=0; for(;x;x-=x&-x) s+=bit[x]; return s;}
inline int getint(){ int s=0,f=1; while((*p!='-')&&(*p<'0'||*p>'9'))p++;
    if(*p=='-')f=-1,p++; while(*p>='0'&&*p<='9')s=s*10+*p++-48; return s*f;
}inline char getop(){
    while(*p!='Q'&&*p!='A'&&*p!='D')p++; return *p++;
}inline void print(int x){
    char str[30],*pt=str; if(!x)*o++=48;
    else{ while(x) *pt++=x%10+48,x/=10; while(pt--!=str)*o++=*pt;}
}int main(){
    fread(p,1,5000000,stdin);
    int q,a,b,k,i=0,t1,t2,An; q=getint();
    for(int qq=1;qq<=q;qq++){
        op=getop();
        if(op=='A'){
            a=getint(),t1=getint(),t2=getint(); b=t2-t1; ++i; A[i]=a; B[i]=b;
            if(a==0){ if(b<0)upd(1,1);}
            else if(b==0){
                if(a<0) upd(1,1),upd(d,-1); else upd(1+d,1);
            }else if(b>0){
                if(a>0){
                    An=b/a+1;
                    if(-r<=An&&An<=r) upd(An+d,1); else if(An<-r) upd(1,1);
                }else{
                    An=b/(-a)+1;
                    if(-r<=-An&&-An<=r) upd(1,1),upd(-An+d+1,-1);
                    else if(-An>r) upd(1,1);
                }
            }else if(b<0){
                if(a>0){
                    An=(-b-1)/a;
                    if(-r<=-An&&-An<=r) upd(-An+d,1); else if(-An<-r) upd(1,1);
                }else{
                    An=(-b-1)/(-a);
                    if(-r<=An&&An<=r) upd(1,1),upd(An+d+1,-1);
                    else if(An>r) upd(1,1);
                }
            }
        }else if(op=='Q'){
            k=getint();
            print(qry(k+d));*o++='\n';
        }else{
            k=getint();
            if(del[k])continue;
            del[k]=1; a=A[k]; b=B[k];
            if(a==0){ if(b<0)upd(1,-1);}
            else if(b==0){
                if(a<0) upd(1,-1),upd(d,1); else upd(1+d,-1);
            }else if(b>0){
                if(a>0){
                    An=b/a+1;
                    if(-r<=An&&An<=r) upd(An+d,-1); else if(An<-r) upd(1,-1);
                }else{
                    An=b/(-a)+1;
                    if(-r<=-An&&-An<=r) upd(1,-1),upd(-An+d+1,1);
                    else if(-An>r) upd(1,-1);
                }
            }else if(b<0){
                if(a>0){
                    An=(-b-1)/a;
                    if(-r<=-An&&-An<=r) upd(-An+d,-1); 
                    else if(-An<-r) upd(1,-1);
                }else{
                    An=(-b-1)/(-a);
                    if(-r<=An&&An<=r) upd(1,-1),upd(An+d+1,1);
                    else if(An>r) upd(1,-1);
                }
            }
        }
    }return fwrite(buf,1,o-buf,stdout),0;
}

以及这是我贡献的一片红色。

• 相关文章