ACdream 1055 Crayon （离散化+树状数组）

ゝ一纸荒年。 2022-06-13 10:15 51阅读 0赞

题目链接：  
[ACdream 1055][]

题意：  
给你 n 个操作，这些操作可以画一条区间大小为 \[L,R\] 的线段，可以删去第 i 条加入的线段，也可以询问区间 \[L,R\] 中有多少个整数点是这些线段共有的。

题解：  
先离散化处理一下，再用树状数组维护一下区间变化即可。  
详细看代码。

AC代码：

#include <bits/stdc++.h>
    using namespace std;
    struct data
    {
        int x,y;
        char ch;
    }d[123456];
    int tree[200010][2];
    int has[200010],all;
    int lowbit(int x)
    {
        return x&(-x);
    
    }
    
    void update(int x,int val,int k)
    {
        while(x<=all)
        {
            tree[x][k] += val;
            x+=lowbit(x);
        }
    }
    int query(int x,int k)
    {
        int res = 0 ;
        while(x)
        {
            res += tree[x][k];
            x -= lowbit(x); 
        }
        return res;
    }
    int solve(int l,int r)
    {
        return query(r,0) - query(l-1,1);
    }
    int main()
    {
        int n;
        while(~scanf("%d",&n))
        {
            all = 0;
            for(int i=1;i<=n;i++)
            {
                getchar();
                scanf("%c",&d[i].ch);
                if(d[i].ch=='C')
                {
                    scanf("%d",&d[i].x);
                    has[all++] = d[i].x;
                }
                else // D , Q 
                {
                    scanf("%d%d",&d[i].x,&d[i].y);
                    has[all++] = d[i].x;
                    has[all++] = d[i].y;
                }
            }
            sort(has,has+all);
            all = unique(has,has+all) - has;
            memset(tree,0,sizeof(tree));
            int cnt = 0;
            for(int i=1;i<=n;i++)
            {
                if(d[i].ch =='D')//draw 
                {
                    int l = lower_bound(has, has+all, d[i].x) - has;
                    int r = lower_bound(has, has+all, d[i].y) - has;
                    update(l+1,1,0);
                    update(r+1,1,1);
                    d[++cnt] = d[i];
                }
                else if(d[i].ch == 'Q') //query 
                {
                    int l = lower_bound(has,has+all,d[i].x) - has;
                    int r = lower_bound(has,has+all,d[i].y) - has;
                    printf("%d\n",solve(l+1,r+1));
                }
                else if(d[i].ch == 'C') //clear 
                {
                    int l = lower_bound(has,has+all,d[d[i].x].x) - has;
                    int r = lower_bound(has,has+all,d[d[i].x].y) - has;
                    update(l+1,-1,0);
                    update(r+1,-1,1);
                }
            }
        }
        return 0;
    }

[ACdream 1055]: http://acdream.info/problem?pid=1055