P5482 [JLOI2011]不等式组 题解

题目传送门


题解

题目理解与强调

首先读入$n$,表示一共进行$n$次操作,每次操作可能有三种形式:

  1. Add a b c:表明要往不等式组添加一条不等式$ax+b>c$。
  2. Del i:代表删除第$i$条添加的不等式(最先添加的是第$1$条)。
  3. Query k:代表一个询问,即当$x=k$时,在当前不等式组内成立的不等式的数量。

注意以下事项:(细节很多)

  1. 一开始不等式组为空,$a,b,c,i,k$均为整数,且保证所有操作均合法,不会出现要求删除尚未添加的不等式的情况,但可能重复删除同一条不等式
  2. 在解不等式的时候,判断$a$的符号,共分三种情况:$a>0$、$a<0$、$a=0$。
  3. 对于一些恒成立或恒不成立的不等式,需要特殊记录。
  4. 因为本题数据范围$k\in[-10^6,10^6]$,所以树状数组按照值域存储,但是要使得数组的下标均为正数,所以要进行离散化。

思路分析

最先想到的,就是化简(解)不等式,如下:

$$\begin{cases}x>\frac{c-b}{a},&a>0\b>c,&a=0\x<\frac{c-b}{a},&a<0\end{cases}$$

然后本题共有两种满分做法:树状数组平衡树(我这个时候不会平衡树)

对于树状数组的解法,根据“题目理解与强调·注意事项”第四条可知,我们要对值域进行存储,整个树状数组$tree[i]$表示$\frac{b-c}{a}$在值域$[i-lowbit(i)+1,i]$(离散化前)出现的次数,用来统计多少个不等式满足答案,但是因为$a$的符号不一定,所以不等号的方向不一定,要开两个树状数组分别表示两种不同形式的解。下面分别讨论三种操作。

对于添加不等式的操作,我们先解出$x$的取值范围。当$a=0$时,如果$b>c$则恒成立,即无论$k$为多少,这个不等式都会对答案做出贡献,当$b<c$时,无论$k$取多少,都不会对答案做出贡献,对于这种恒成立或恒不成立的情况,我们要做出记录,设$cnt$记录恒成立的不等式的数量,同时要开设数组用于之后的删除判断$k[x]$,$x$表示第$x$个不等式的解的情况,代码中$k[x]$值为$0$表示恒不成立,值为$1$表示解的形式为$x>\frac{c-b}{a}$值为$2$表示解的形式为$x<\frac{c-b}{a}$,值为$3$表示不等式恒成立。对于其他情况的存储,我们放在两个树状数组中,一个表示$x>\frac{c-b}{a}$类型的解,另一个表示$x<\frac{c-b}{a}$的解,树状数组中的下标的是$\frac{c-b}{a}$,但是$\frac{c-b}{a}$的值不一定为整数,所以我们再次分类讨论,当$a>0$时即方程的解为$x>\frac{b-c}{a}$时,我们要对存储的答案进行下取整,举个例子,若我得出一个结果$x>1.5$,给出$k=2$,如果我上取整了,那么这个点会被忽略,实际上$x>1.5$也是符合要求的,所以下取整,反之(对于$x<\frac{c-b}{a}$),我们要对这个值上取整。

对于查询操作,我们要同时从两个树状数组和特殊不等式中找答案,在存储$“>”$的树中,我们要找小于等于$k$的值的数量,直接输出树状数组中的前缀(记得加上之前离散化所加的值)即可,在存储$“<”$的树中,我们要找到大于$k$的值的数量,此时输出树状数组中的后缀(右端点前缀减左端点前缀),两数相加,再加上恒成立的不等式的数量。

对于删除操作,我们利用添加不等式的函数,将树状数组中所记录的有关这个不等式的值减$1$,或者将恒成立的不等式数量减$1$,同时记录下删除了哪些不等式,防止删重。

文字思路不清晰?看代码!


代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define ll long long
#define ull unsigned long long
#define reg register
#define PI acos(-1.0)
#define pb(x) push_back(x)
#define mp(a,b) make_pair(a,b)
#define fi first
#define se second
#define pr(x) cerr<<#x<<"="<<(x)<<endl
#define pri(x,lo) {cerr<<#x<<"={";for (int ol=0;ol<=lo;ol++)cerr<<x[ol]<<",";cerr<<"}"<<endl;}
#define inf 100000000
#define N 1000
#define M 1000010
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*10+ch-48;ch=getchar();}
    return x*f;
}
int s[2*M],tree1[2*M],tree2[2*M],k[2*M],n,cnt,top,vis[2*M];//k[]表示不等式类型,tree1/2[]表示两组树状数组,cnt表示恒成立的不等式的数量,vis[]记录哪个不等式被删除
char c[10];
int lowbit(int x)
{
    return x&-x;
}
void build1(int x,int p)
{
    x+=M;
    while(x<=2*M)
    {
        tree1[x]+=p;
        x+=lowbit(x);
    }
    return;
}
void build2(int x,int p)
{
    x+=M;
    while(x<=2*M)
    {
        tree2[x]+=p;
        x+=lowbit(x);
    }
    return;
}
int search1(int x)
{
    x+=M;
    int sum=0;
    while(x)
    {
        sum+=tree1[x];
        x-=lowbit(x);
    }
    return sum;
}
int search2(int x)
{
    x+=M;
    int sum=0;
    while(x)
    {
        sum+=tree2[x];
        x-=lowbit(x);
    }
    return sum;
}
int main()
{
    n=read();
    while(n--)
    {
        while(1)
        {
            scanf("%s",c);
            if(c[0]=='A')
            {
                int a=read(),b=read(),c=read();
                if(a==0)
                {
                    if(b>c)
                    {
                        cnt++;
                        k[++top]=3;
                    }
                    else
                        k[++top]=0;
                }
                else if(a>0)
                {
                    s[++top]=floor((c*1.0-b)/(a*1.0));
                    k[top]=1;
                    if(s[top]>1e6)
                        k[top]=0;
                    else if(s[top]<-1e6)
                    {
                        cnt++;
                        k[top]=3;
                    }
                    else
                        build1(s[top],1);
                }
                else if(a<0)
                {
                    s[++top]=ceil((c*1.0-b)/(a*1.0));
                    k[top]=2;
                    if(s[top]<-1e6)
                        k[top]=0;
                    else if(s[top]>1e6)
                    {
                        cnt++;
                        k[top]=3;
                    }
                    else
                        build2(s[top],1);
                }
                break;
            }
            if(c[0]=='Q')
            {
                int a=read(),sum;
                sum=search1(a-1)+search2(1e6)-search2(a)+cnt;
                printf("%d\n",sum);
                break;
            }
            if(c[0]=='D')
            {
                int a=read();
                if(vis[a]==1)   break;
                vis[a]=1;
                if(k[a]==3) cnt--;
                if(k[a]==1) build1(s[a],-1);
                if(k[a]==2) build2(s[a],-1);
                break;
            }
        }
    }
    return 0;
}
文章标题:P5482 [JLOI2011]不等式组 题解
文章链接:https://www.laoguantx.top/p5482-jloi2011%e4%b8%8d%e7%ad%89%e5%bc%8f%e7%bb%84-%e9%a2%98%e8%a7%a3.html
文章内容仅供参考,其中可能会有部分内容参考、引用其他网站,转发请务必标注作者为 “老官童鞋gogo” ,原文链接为 https://www.laoguantx.top/p5482-jloi2011%e4%b8%8d%e7%ad%89%e5%bc%8f%e7%bb%84-%e9%a2%98%e8%a7%a3.html 。
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇