题外话：维护区间交集子集的小套路
开两个树状数组，一个维护进入区间，一个维护退出区间
$Query:$
给定询问区间$l,r$和一些其他区间，求其他区间中与$[l,r]$交集非空的区间个数
用上面维护的信息表示，就是$r$（含）前进入的区间个数$-l$（不含）前退出的区间个数
这个题：
我们可以把它抽象为，求区间对个数，要求区间对交集非空且互不包含
尝试像上面那样解决，$l$后进入$-r$后进入保证左端点满足要求，$l$后进入$-r$前退出，右端点满足要求
但是放到一起好像就有些问题了，尝试减掉一个条件，不妨按左端点从右向左依次插入树状数组，消掉$l$后进入这个条件
这样，查询就变成了$r$前进入$-r$前退出，我们就可以顺利解决这道题了
#include<iostream> #include<cstdio> #include<vector> #include<algorithm> using namespace std; const int maxn=50010; int n,ans,a[2*maxn],c[2][2*maxn]; vector<int>v[maxn]; int lowbit(int x) { return x&-x; } int sum(int id,int x) { int ret=0; while(x) { ret+=c[id][x]; x-=lowbit(x); } return ret; } void add(int id,int x) { while(x<=2*n) { c[id][x]++; x+=lowbit(x); } } int main() { scanf("%d",&n); for(int i=1;i<=2*n;i++) { scanf("%d",&a[i]); v[a[i]].push_back(i); } for(int i=2*n;i;i--) if(v[a[i]][0]==i) { int r=v[a[i]][1]; ans+=sum(0,r)-sum(1,r); add(0,v[a[i]][0]),add(1,v[a[i]][1]); } printf("%d ",ans); return 0; }