【题解】CF1401E

我们定义特殊线段为一个端点为 $0$，另一个端点为 $10^6$ 的线段。

然后瞎猜一个看上去十分不靠谱的结论：

$\text{ans}=\text{线段交点个数}+\text{特殊线段个数}+1$

然后你发现它过了

考虑两根线段，如果它们相交则必然产生恰好 $1$ 个块。这很好理解，因为每根线段都有至少一个端点在边界上。

普通线段不会产生在此之外的贡献，而特殊线段们自己就可以产生 $1$ 的贡献。

交点个数则是一个经典树状数组问题：用值域为 $1\sim 10^6$ 的树状数组维护水平的线段。将垂直线段按横坐标从小到大排序，枚举竖直线段的同时维护水平线段。

// 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;
}

附：现 场 回 放