洛谷P2184——贪婪大陆

比眉伴天荒 2023-06-05 12:44 17阅读 0赞

传送门：[QAQQAQ][]

题意：给一个长度为$n$的区间，每次可以进行两种操作：

1.在$\[l,r\]$这个区间里放置一个和之前种类不同的炸弹

2.查询在$\[l,r\]$区间内有多少种不同种类的炸弹

思路：第一反应是线段树：但一直没想出来线段树来维护什么

和？和可能会因为炸弹覆盖区间长度为改变，而不是因为炸弹种类而改变。

最大值？可能两个完全不相交的区间却有两种不同的炸弹

所以我们要换一个思路想：我们可以把题目转化成这样：给你一个区间，求之前那些区间和该区间相交的有几个

再想：两个区间相交有什么特点呢？两个区间相离又有什么特点呢？——两个区间相离要么是$l1>r2$，要么是$r1<l2$

我们就很容易找到思路了：我们建立两个线段树分别维护区间内$l,r$分别出现的次数

然后对于每一个询问的$l,r$，在$\[1,l-1\]$区间内查询$r$有几个（cnt1），在$\[r+1,n\]$查询$l$有几个（cnt2），然后用之前的总区间个数减去($cnt1+cnt2$)即可。

（思路很像CF1190D，维护位置存在点的个数，一般这种题都要用离散化（莫名又想到CDQ分治……））

代码：（线段树当然可以，但树状数组似乎更方便）

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    const int N=100050;
    
    int sum[2][N*4],n,m;//0:l 1:r
    void build(int x,int l,int r)
    {
        if(l==r) 
        {
            sum[1][x]=0;
            sum[0][x]=0;
            return;
        }
        int mid=(l+r)>>1;
        build(x+x,l,mid);
        build(x+x+1,mid+1,r);
    }
    
    void update(int x,int l,int r,int pos,int bl)
    {
        if(l==r) 
        {
            sum[bl][x]++;
            return;
        }
        int mid=(l+r)>>1;
        if(mid>=pos) update(x+x,l,mid,pos,bl);
        else update(x+x+1,mid+1,r,pos,bl);
        sum[bl][x]=sum[bl][x+x]+sum[bl][x+x+1];
    }
    
    int query(int x,int l,int r,int L,int R,int bl)
    {
        int ret=0;
        if(L>R) return 0;
        if(L<=l&&r<=R) return sum[bl][x];
        int mid=(l+r)>>1; 
        if(mid>=L) ret+=query(x+x,l,mid,L,R,bl);
        if(mid<R) ret+=query(x+x+1,mid+1,r,L,R,bl);
        return ret;
    }
    
    int main()
    {
        int sum=0;
        scanf("%d%d",&n,&m);
        while(m--)
        {
            int x,y,opt;
            scanf("%d%d%d",&opt,&x,&y);
            if(opt==1)
            {
                update(1,1,n,x,0);
                update(1,1,n,y,1);
                sum++;
            }
            else
            {
                int now=0;
                now+=query(1,1,n,y+1,n,0);
                now+=query(1,1,n,1,x-1,1);
                printf("%d\n",sum-now);
            }
        }
        return 0;
    }

转载于:https://www.cnblogs.com/Forever-666/p/11306355.html

[QAQQAQ]: https://www.luogu.org/problem/P2184
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/ef81b3f8690448f9b402d0c02c227c60.png