我们定义特殊线段为一个端点为 ,另一个端点为 的线段。
然后瞎猜一个看上去十分不靠谱的结论:
然后你发现它过了
考虑两根线段,如果它们相交则必然产生恰好 个块。这很好理解,因为每根线段都有至少一个端点在边界上。
普通线段不会产生在此之外的贡献,而特殊线段们自己就可以产生 的贡献。
交点个数则是一个经典树状数组问题:用值域为 的树状数组维护水平的线段。将垂直线段按横坐标从小到大排序,枚举竖直线段的同时维护水平线段。
// 2020.08.21
// by LTb
// #pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define debug cout<<"QwQ"<<endl;
inline int read(){
int x=0,f=1;
char ch;
while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return f*x;
}
const int MAXN=100005;
const int MAX=1e6;
int n,m;
int a[MAXN];
struct BIT{
int tree[MAX+10];
int Max_Value=n;
inline int lowbit(int x){
return x&(-x);
}
inline void add(int x,int c){
while (x<=Max_Value+1){
tree[x]+=c;
x+=lowbit(x);
}
}
inline int query(int x){
int ans=0;
while (x>0){
ans+=tree[x];
x-=lowbit(x);
}
return ans;
}
inline int query2(int l,int r){
return query(r)-query(l-1);
}
inline void add2(int l,int r,int c){
add(l,c);
add(r+1,-c);
}
}t;
vector<pair<int,int> > v[MAX+10];
struct node{
int x,l,r;
bool operator<(node b){
return x<b.x;
}
}q[MAXN];
signed main()
{
n=read();m=read();
t.Max_Value=MAX+2;
int ans=1;
for (int i=1;i<=n;i++){
int x=read(),l=read(),r=read();
if (l==0 && r==MAX) ans++;
v[l].push_back(make_pair(x,1));
v[r+1].push_back(make_pair(x,-1));
}
for (int i=1;i<=m;i++){
q[i].x=read();q[i].l=read();q[i].r=read();
if (q[i].l==0 && q[i].r==MAX) ans++;
}
sort(q+1,q+1+m);
int cur=0;
for (int i=1;i<=m;i++){
while (cur<=q[i].x){
for (auto j:v[cur])
t.add(j.first,j.second);
cur++;
}
int tmp=t.query2(q[i].l,q[i].r);
ans+=tmp;
}
cout<<ans<<endl;
return 0;
}
附:现 场 回 放