题解 P2184 【贪婪大陆】

首先观察题目实质： 1.扔一个区间[l,r] 2.查询有多少个之前插入过的区间与[l,r]有交 回忆我们线段树如何判断当前节点代表的区间[l,r]与询问区间[L,R]没有交集 ```cpp if (l>R||r<L)return 0; ``` 没有交集是l>R||r<L那么有交集就是!(l>R||r<L)=l<=R&&r>=L 然后这就变成了一个二维偏序问题 $$r>=L.l<=R$$ (l,r代表之前插入过的所有区间,L,R代表查询区间) 然后这个玩意如果在线的话显然可以直接树套树直接爆搞 去cdq分治离线你就要加一维时间变成三维偏序非常不爽 什么两个树状数组线段树做法我太菜了不会 然后我就用了个$KDtree$维护这个二维偏序 要动态插入，替罪羊思想重构即可 ```cpp #include<cstdio> #include<algorithm> using std::nth_element; template<class type>inline const void read(type &in) { in=0;char ch=getchar();bool f=0; while (ch<48||ch>57){if (ch=='-')f=1;ch=getchar();} while (ch>47&&ch<58)in=(in<<3)+(in<<1)+(ch&15),ch=getchar(); if (f)in=-in; } template<class type>inline const void write(type out) { if (out>9)write(out/10); putchar(out%10+48); } template<class type>inline const void writeln(type out) { if (out<0)out=-out,putchar('-'); write(out); putchar('\n'); } template<class type>inline const type max(const type &a,const type &b) { return a>b?a:b; } template<class type>inline const type min(const type &a,const type &b) { return a<b?a:b; } const int N=1e5+10,inf=2147483647,K=2; int n,m; int f; struct point { int d[K]; inline point(const int &x=0,const int &y=0){d[0]=x;d[1]=y;} inline const bool operator<(const point &p)const { return d[f]<p.d[f]; } }; template<int k>class KD_Tree { private: static const double alpha=0.75; struct tree { int size; tree *son[2]; point range,mx,mn; inline const void pushup() { size=son[0]->size+1+son[1]->size; for (int i=0;i<k;i++) mn.d[i]=min(range.d[i],min(son[0]->mn.d[i],son[1]->mn.d[i])), mx.d[i]=max(range.d[i],max(son[0]->mx.d[i],son[1]->mx.d[i])); } inline const bool at(const point &lower,const point &upper) { for (int i=0;i<k;i++) if (!(range.d[i]>=lower.d[i]&&range.d[i]<=upper.d[i])) return 0; return 1; } inline const bool in(const point &lower,const point &upper) { for (int i=0;i<k;i++) if (!(mn.d[i]>=lower.d[i]&&mx.d[i]<=upper.d[i])) return 0; return 1; } inline const bool out(const point &lower,const point &upper) { for (int i=0;i<k;i++) if (mn.d[i]>upper.d[i]||mx.d[i]<lower.d[i]) return 1; return 0; } inline const bool unbalanced() { return son[0]->size>size*alpha||son[1]->size>size*alpha; } }*root,memory_pool[N],*tail,*null,*recycle[N]; int top,flag,cnt; point a[N]; inline const void init() { tail=memory_pool; null=tail++; root=null->son[0]=null->son[1]=null; for (int i=0;i<k;i++)null->mn.d[i]=inf,null->mx.d[i]=-inf; } inline tree *spawn(const point &x) { tree *p=top?recycle[--top]:tail++; p->size=1; p->range=p->mx=p->mn=x; p->son[0]=p->son[1]=null; return p; } inline const void travel(tree *p) { if (p==null)return; travel(p->son[0]); a[++cnt]=p->range; recycle[top++]=p; travel(p->son[1]); } inline tree *build(int l,int r,int d) { if (l>r)return null; int mid=l+r>>1;f=d; nth_element(a+l,a+mid,a+r+1); tree *p=spawn(a[mid]); if (l==r)return p; p->son[0]=build(l,mid-1,(d+1)%k); p->son[1]=build(mid+1,r,(d+1)%k); p->pushup(); return p; } inline const void rebuild(tree *&p,int d) { cnt=0; travel(p); p=build(1,cnt,d); } inline tree **insert(tree *&p,const point &x,int d) { if (p==null)return p=spawn(x),&null; tree **bad=insert(p->son[p->range.d[d]<x.d[d]],x,(d+1)%k); p->pushup(); if (p->unbalanced())bad=&p,flag=d; return bad; } inline const int query(tree *p,const point &x,const point &y) { if (p==null)return 0; if (p->out(x,y))return 0; if (p->in(x,y))return p->size; return p->at(x,y)+query(p->son[0],x,y)+query(p->son[1],x,y); } public: inline KD_Tree(){init();} inline const void insert(int x,int y) { tree **bad=insert(root,point(x,y),flag=0); if (*bad==null)return; rebuild(*bad,flag); } inline const int query(int x1,int y1,int x2,int y2) { return query(root,point(x1,y1),point(x2,y2)); } }; KD_Tree<K>kdt; int main() { read(n);read(m); for (int opt,l,r;m--;) if (read(opt),read(l),read(r),opt&1)kdt.insert(l,r); else writeln(kdt.query(-inf,l,r,inf)); return 0; } ```