【bzoj2762】[JLOI2011]不等式组

2015.01.29 22:03 Thu | 4次阅读 | 旧日oi | 固定链接 | 源码

Description

旺汪与旺喵最近在做一些不等式的练习。这些不等式都是形如ax+b>c 的一元不等式。当然,解这些不等式对旺汪来说太简单了,所以旺喵想挑战旺汪。旺喵给出一组一元不等式,并给出一个数值 。旺汪需要回答的是x=k 时成立的不等式的数量。聪明的旺汪每次都很快就给出了答案。你的任务是快速的验证旺汪的答案是不是正确的。

Input

输入第一行为一个正整数 ,代表接下来有N 行。
接下来每一行可能有3种形式:
1.“Add a b c”,表明要往不等式组添加一条不等式ax+b>c ;
2.“Del i”,代表删除第i 条添加的不等式(最先添加的是第1条)。
3.“Query k”,代表一个询问,即当x=k 时,在当前不等式组内成立的不等式的数量。
注意一开始不等式组为空,a,b,c,i,k 均为整数,且保证所有操作均合法,不会出现要求删除尚未添加的不等式的情况。

Output

对于每一个询问“Query k”,输出一行,为一个整数,代表询问的答案。

Sample Input

9
Add 1 1 1
Add -2 4 3
Query 0
Del 1
Query 0
Del 2
Query 0
Add 8 9 100
Query 10

Sample Output

1
1
0
0

HINT

第1条添加到不等式组的不等式为x+1>1 ,第2条为-2x+4>3 ,所以第1个询问的时候只有第2条不等式可以成立,故输出1。
然后删除第1条不等式,再询问的时候依然是只有第2条不等式可以成立,故输出1。
再删除第2条不等式后,因为不等式组里面没有不等式了,所以没有不等式可以被满足,故输出0。
继续加入第3条不等式8x+9>100 ,当x=k=10时有8*10+9=89<100,故也没有不等式可以被满足,依然输出0。
数据范围:
20%的数据, N<=1000;
40%的数据, N<=10000;
100%的数据,N<=100000,
a,b,c的范围为[-10^8,10^8],k的范围为[-10^6,10^6]。

题解

吉林OI真是恶心啊……受不鸟……不过还是要先刷掉所有的吉林省省选!!
看懂题之后就会发现直接用树状数组就可以搞定
这里我用了两个,一个是记录斜率为正的,一个是记录斜率为负的,看代码就可以明白了
比较恶心的地方就是求每个方程的解,需要判断的情况不少,代码写的还是比较易懂的。我开始一直以为-3/2=-2,所以wa了好多次,后来看了数据才发现这个问题……费了将近一个晚上,不过也是值得的,起码以后不会再犯了,也总比以后比赛出现这种题白白丢掉60分强

我的程序

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#define maxn 100005
using namespace std;
int n,x,y,z,cnt,ans,q;
int ask[maxn];
bool flag[maxn];
char s[10];
int c1[2000005],c2[2000005];
int solve(int a,int b,int c)
{
    if(a==0) return b>c?-1000000:1000001;
    if(a>0) 
    {
        int k;
        if(c-b>0) k=(c-b)/a+1;
        else if(c-b==0) k=1;
        else if((c-b)%a==0) k=(c-b)/a+1;
        else k=(c-b)/a;
        //if(abs(k+291920)<=1) cout<<a<<"***************"<<b<<" "<<c<<" "<<k<<endl;
        if(k>1000000) return 1000001;
        if(k<-1000000) return -1000000;
        return k;
    }
    else
    {
        int k;
        if((c-b)==0) k=-1;
        else if(c-b>0) k=(c-b)/a-1;
        else if((c-b)%a==0) k=((c-b)/a)-1;
        else k=((c-b)/a);
        //if(abs(k+291920)<=1)cout<<a<<"***************"<<b<<" "<<c<<" "<<k<<endl;
        if(k>1000000) return 1000000;
        if(k<-1000000) return -1000001;
        return k;
    }
}
int lowbit(int x)
{
    return x&(-x);
}
void add(int x,int num,bool f)
{
    if(f) for(int i=x;i<=2000001;i+=lowbit(i))c1[i]+=num;
    else for(int i=x;i;i-=lowbit(i)) c2[i]+=num;
}
int query(int x)
{
    int ret=0;
    for(int i=x;i;i-=lowbit(i)) ret+=c1[i];
    for(int i=x;i<=2000001;i+=lowbit(i)) ret+=c2[i];
    return ret;
}
int main()
{
    //freopen("inequal.in","r",stdin);
    //freopen("inequal.out","w",stdout);
    cin>>n;
    while(n--)
    {
        scanf("%s%d",s,&x);
        if(s[0]=='A')
        {
            scanf("%d%d",&y,&z);
            int k=solve(x,y,z);
            flag[++cnt]=(x>=0)?1:0;
            if(k>1000000||k<-1000000) 
            {
                ask[cnt]=0;
                continue;
            }
            ask[cnt]=k+1000001;
            add(ask[cnt],1,flag[cnt]);
        }
        else if(s[0]=='D') 
        {
            if(ask[x]==0) continue;
            if(flag[x]&&ask[x]<-291920) ans--;
            if(!flag[x]&&ask[x]>-291920) ans--;
            add(ask[x],-1,flag[x]);
            ask[x]=0;
        }
        else printf("%d\n",query(x+1000001));
    }
}```