Eternity

Until The End

P5482 [JLOI2011]不等式组

发表于 分类于
本文字数： 182 阅读时长 ≈ 1 分钟

细节很多的平衡树板子。

题目链接

拿到这道题之后不到五分钟就口胡出来了，然后细节调了半个多小时。

我们把不等式进行一个变式：

然后，建立平衡树查找比当前 $k$ 小和大的个数即可。

对于负数和正数分别建立。

然后就是很多很多的细节：

  • 对于 $a=0$ 的情况，可能是恒成立，也可能是恒不成立，这里可以添加 $delta$ 来特判；
  • 对于删除过的不等式，再删除的时候，就不能再删了，这里建立哈希 $del[x]$ 判断是否被删除过；
  • 对于 $a=0$ 的特判一定要在计算之前进行，否则会因为除以 $0$ 而导致 $\text{RE}$ 。
  • 每个人的实现方式都不同，所以一定要想好那个等于到底取不取。
AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline void write(T x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
const int MAXN=1e5+10;
const int INF=0x3f3f3f3f;
int Q,Cnt,delta;
int Val[MAXN],Id[MAXN];
bool Del[MAXN];
struct B_T
{
    int Idx=0,Rt;
    int x,y,z;
    struct Fhq
    {
        int val,rd,siz,chi[2];
    }Tr[MAXN];
    #define ls(p) Tr[p].chi[0]
    #define rs(p) Tr[p].chi[1]
    inline void upDate(int p)
    {
        Tr[p].siz=Tr[ls(p)].siz+Tr[rs(p)].siz+1;
    }
    inline int newNode(int v)
    {
        Tr[++Idx]=(Fhq){v,rand(),1};
        return Idx;
    }
    inline void split(int p,int k,int &u,int &v)
    {
        if(!p) u=v=0;
        else
        {
            if(Tr[p].val<=k) u=p,split(rs(u),k,rs(u),v);
            else v=p,split(ls(v),k,u,ls(v));
            upDate(p);
        }
    }
    inline int merge(int u,int v)
    {
        if(!u||!v) return u+v;
        if(Tr[u].rd<Tr[v].rd)
        {
            rs(u)=merge(rs(u),v);
            return upDate(u),u;
        }
        else
        {
            ls(v)=merge(u,ls(v));
            return upDate(v),v;
        }
    }
    inline void insert(int v)
    {
        split(Rt,v,x,y);
        Rt=merge(merge(x,newNode(v)),y);
    }
    inline void del(int v)
    {
        split(Rt,v,x,z),split(x,v-1,x,y);
        y=merge(ls(y),rs(y));
        Rt=merge(merge(x,y),z);
    }
    inline int nxt(int v)
    {
        split(Rt,v,x,y);
        int res=Tr[y].siz;
        Rt=merge(x,y);
        return res;
    }
    inline int pre(int v)
    {
        split(Rt,v-1,x,y);
        int res=Tr[x].siz;
        Rt=merge(x,y);
        return res;
    }
}Max,Min;
char opt[10];
inline int calc(double c,double u,double v)
{
    if(c>0) return std::floor((v-u)/c);
    else return std::ceil((v-u)/c);
}
int main()
{
    // freopen("fhq-treap.in","r",stdin);
    // freopen("fhq-treap.out","w",stdout);
    srand(time(NULL));
    read(Q);
    for(int u,v,c;Q--;)
    {
        scanf("%s",opt+1);read(c);
        if(opt[1]=='A')
        {
            read(u,v);
            if(c==0)
            {
                Id[++Cnt]=-114514;
                if(u>v) ++delta,Id[Cnt]*=-1;
                continue;
            }
            Val[++Cnt]=calc(c,u,v);
            if(c<0) Id[Cnt]=-1,Min.insert(Val[Cnt]);
            else if(c>0) Id[Cnt]=1,Max.insert(Val[Cnt]);
        }
        else if(opt[1]=='D')
        {
            if(Del[c]) continue;
            if(Id[c]==114514) --delta;
            else if(Id[c]==-1) Min.del(Val[c]);
            else Max.del(Val[c]);
            Del[c]=1;
        }
        else write(delta+Max.pre(c)+Min.nxt(c)),puts("");
    }
    // for(int i=1;i<=Cnt;++i) printf("%d %d\n",Val[i],Id[i]);
    return 0;
}
/*
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
*/
相关文章