题目大意

给你$N$个集合,编号从$1$到$N$,初始都为空。
你的任务是完成以下两种操作:

  • 0 l r x将数字$x$添加到第$l$个到第$r$个集合中。(注意给定的是集合,根据定义,集合不包含重复元素。所以一个数字可以添加到一个集合中当且仅当该集合中不包含这个数字。)
  • 1 q输出第$q$个集合中的元素个数。

这题非常有意思QwQ

首先看到维护真·集合,所以常用的套路就是不可以的了。发现区间个数为$N$,此时就大概可以想到大力合并的时间复杂度是对的。用set<pair<int,int> >来记录每个数的出现区间,大力合并一下,时间复杂度$O(N \log N)$.

注意有一种特殊情况是你想用区间覆盖的某个区间实际上覆盖新插入的这个区间,这种时候特判一下就过了。

又debug又对拍……绝了。

#include <set>
#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,bit[250010];
set<pair<int,int> >st[250010];
void update(int x,int y)
{
    int i;
    for(i=x;i<=n;i+=i&-i) bit[i]+=y;
    return;
}
int query(int x)
{
    int i,ret=0;
    for(i=x;i;i-=i&-i) ret+=bit[i];
    return ret;
}
void modify(int l,int r,int x)
{
    int tl=l,tr=r;
    set<pair<int,int> >::iterator it=st[x].lower_bound(pair<int,int>(l,0)),jt;
    if(it!=st[x].end()&&it->first>=r&&it->second<=l) return;
    for(it=st[x].lower_bound(pair<int,int>(l,0));it!=st[x].end()&&((it->first>=tl&&it->first<=tr)||(it->second>=tl&&it->second<=tr));jt=it,++it,st[x].erase(jt))
    {
        tl=min(tl,it->second),tr=max(tr,it->first);
        update(it->second,-1),update(it->first+1,1);
    }
    st[x].insert(pair<int,int>(tr,tl)),update(tl,1),update(tr+1,-1);
    return;
}
int main()
{
    freopen("dp.in","r",stdin);
    int opt,l,r,x;
    scanf("%d%d",&n,&m);
    while(m--)
    {
        scanf("%d",&opt);
        switch(opt)
        {
            case 0:scanf("%d%d%d",&l,&r,&x),modify(l,r,x);break;
            case 1:scanf("%d",&x),printf("%d\n",query(x));break;
        }
    }
    return 0;
}