[Solution][Data Structure][Treap]JLOI2011 不等式组

【题目】

戳这里

【题意】

支持若干操作:插入一个形如的不等式;删除某个不等式;对于给定某整数k询问满足的不等式数目。

【思路】

维护两颗平衡树,一个维护可化为的不等式,一个维护可化为的不等式,对于a=0的特殊讨论。
具体实现时,Treap中维护的是

这样可以避免实数运算。

记录一下每个不等式插入的值和插入到哪颗平衡树中,删除时按值删除一个。(可能会删除已经删除过的。。。)
询问时就查一查,再加上对于a=0的不等式的处理。
时间复杂度.

【代码】

/**************************************************************
    Problem: 2762
    User: wyfcyx
    Language: C++
    Result: Accepted
    Time:956 ms
    Memory:6000 kb
****************************************************************/
 
#include<cstdio>
#include<cstdlib>
#include<cctype>
#include<cstring>
#define clear(x , y) memset(x , y , sizeof(x))
const int N = 100001;
int save[N] , hash[N] , should_add[N];
bool deleted[N];
inline int getint()
{
    char c = 0;
    while(!isdigit(c) && c != '-')
        c = getchar();
    bool un = c == '-';
    int tmp = un ? 0 : c - '0';
    while(isdigit(c = getchar()))
        tmp = (tmp << 1) + (tmp << 3) + c - '0';
    return un ? -tmp : tmp;
}
struct Treap
{
    int l[N] , r[N] , v[N] , p[N] , s[N] , root , size_num;
    bool sign;
    Treap()
    {
        clear(l , 0);
        clear(r , 0);
        clear(v , 0);
        clear(p , 0);
        clear(s , 0);
        root = 0;
        sign = 0;
        size_num = 0;
    }
    void maintain(int &q)
    {
        s[q] = s[l[q]] + 1 + s[r[q]];
    }
    void lr(int &q)
    {
        int tmp = r[q];
        r[q] = l[tmp];
        l[tmp] = q;
        maintain(q);
        maintain(tmp);
        q = tmp;
    }
    void rr(int &q)
    {
        int tmp = l[q];
        l[q] = r[tmp];
        r[tmp] = q;
        maintain(q);
        maintain(tmp);
        q = tmp;
    }
    int newnode(int x , int ord)
    {
        static int q = 1;
        l[q] = r[q] = 0;
        p[q] = rand();
        s[q] = 1;
        v[q] = x;
        hash[ord] = (q << 1) | sign;
        return q++;
    }
    void insert(int x , int &q , int ord)
    {
        if (!q)
            q = newnode(x , ord);
        else if (x < v[q])
        {
            insert(x , l[q] , ord);
            if (p[q] < p[l[q]])
                rr(q);
        }
        else
        {
            insert(x , r[q] , ord);
            if (p[q] < p[r[q]])
                lr(q);
        }
        maintain(q);
    }
    void remove(int x , int &q)
    {
        if (!q)
            return;
        else if (x == v[q])
        {
            if (!l[q] || !r[q])
            {
                if (!l[q])
                    q = r[q];
                else
                    q = l[q];
            }
            else if (p[l[q]] < p[r[q]])
            {
                rr(q);
                remove(x , r[q]);
            }
            else
            {
                lr(q);
                remove(x , l[q]);
            }
        }
        else if (x < v[q])
            remove(x , l[q]);
        else
            remove(x , r[q]);
        if (q)
            maintain(q);
    }
    int lower_bound(int x , int &q)
    {
        if (!q)
            return 1;
        else if (x <= v[q])
            return lower_bound(x , l[q]);
        else
            return s[l[q]] + 1 + lower_bound(x , r[q]);
    }
    int upper_bound(int x , int &q)
    {
        if (!q)
            return 1;
        else if (x < v[q])
            return upper_bound(x , l[q]);
        else
            return s[l[q]] + 1 + upper_bound(x , r[q]);
    }
   
}Big , Small;
int main()
{
    
    int Ask;
    char s[21];
    int a , b , c , now_num = 0 , add_ans = 0;
    Small.sign = 0;
    Big.sign = 1;
    scanf("%d" , &Ask);
    while(Ask--)
    {
        scanf("%s" , s);
        if (s[0] == 'A')
        {
            ++now_num;
            a = getint() , b = getint() , c = getint();
            if (a == 0)
            {
                if (b > c)
                {
                    should_add[now_num] = 1;
                    ++add_ans;
                }
                else
                    should_add[now_num] = 2;
            }
            else
            {
                int now_ins;
                if (a > 0)
                {
                    if ((c - b) % a == 0) 
                        now_ins = (c - b) / a + 1;
                    else
                        now_ins = int((c - b) / double(a)) + ((c - b > 0) ? 1 : 0);
                    save[now_num] = now_ins;
                    Big.insert(now_ins , Big.root , now_num);
                    ++Big.size_num;
                    
                }
                else
                {
                    if ((c - b) % a == 0)
                        now_ins = ((c - b) / a) - 1;
                    else
                        now_ins = int((c - b) / double(a)) - ((c - b > 0) ? 1 : 0);
                    save[now_num] = now_ins;
                    Small.insert(now_ins , Small.root , now_num);
                    ++Small.size_num;
                }
            }
        }
        if (s[0] == 'D')
        {
            a = getint();
            if (should_add[a])
            {
                if (should_add[a] == 1)
                {
                    if (!deleted[a])
                    {
                        deleted[a] = 1;
                        --add_ans;
                    }
                }
            }
            else
            {
                if (!deleted[a])
                {
                    deleted[a] = 1;
                    if (hash[a] & 1)
                    {
                        Big.remove(save[a] , Big.root) , --Big.size_num;
                        
                    }
                    else
                    {
                        Small.remove(save[a] , Small.root) , --Small.size_num;
                        
                    }
                }
            }
        }
        if (s[0] == 'Q')
        {
            a = getint();
            int ans = add_ans;
            ans += Big.upper_bound(a , Big.root) - 1;
            ans += Small.size_num - Small.lower_bound(a , Small.root) + 1;
            printf("%d\n" , ans);
        }
    }
    return 0;
}
comments powered by Disqus