题面
给一个正方形平面边长为 (10^6)，给 (n) 条横线段和 (m) 条竖线段，每条线段都与正方形边缘相交且一条直线上不会有两条线段，求被线段划分后有几个块。
数据范围：(0le n,mle 10^5)，(0<x,y<10^6)，(0le (lx<rx),(ly<ry)le 10^6)。
蒟蒻语
前天打小号 (30) 分钟切了 ( t ABCD) 以为能 ( t AK)，结果 ( t E) 少看了条件开始硬钢幸得爆零。
蒟蒻解
结论：(ans=()内部交点数 (p)+(10^6) 长度线段数 (s)+1)。
这个结论应该比较好找，可以多画几个图找规律。
蒟蒻本来想了一个很炫酷的证明，但被证伪了，看个逊一点的吧……
证明：
对于 (s=0) 的情况，所有线段都贴且仅贴一边又互相不重合，所以每多一个交点多一个块易证。
对于 (s>0) 的情况，如果一条长度为 (10^6) 的线段不穿过线段，那么固然把正方形分成两块多一块。否则从一条被穿过的线段把它拆成两条线段考虑，答案也会 (+1)。
综上，(ans=p+s+1)。
至于实现，可以用树状数组扫描线，代码中给出一种新奇的树状数组写法。
代码
#include <bits/stdc++.h>
using namespace std;
//Start
typedef long long ll;
typedef double db;
#define mp(a,b) make_pair((a),(b))
#define x first
#define y second
#define be(a) (a).begin()
#define en(a) (a).end()
#define sz(a) int((a).size())
#define pb(a) push_back(a)
#define R(i,a,b) for(int i=(a),I=(b);i<I;i++)
#define L(i,a,b) for(int i=(a),I=(b);i>I;i--)
const int iinf=0x3f3f3f3f;
const ll linf=0x3f3f3f3f3f3f3f3f;
//Data
const int N=1e5,M=1e6;
int n,m; ll ans=1;
vector<int> d;
struct segment{
int op,y,l,r;
segment(){}
segment(int _op,int _y,int _l,int _r){
op=_op,y=_y,l=_l,r=_r;
}
};
vector<segment> a;
//FenwickTree
vector<int> c;
void add(int i,int v){for(;i<sz(c);i|=i+1) c[i]+=v;}
int sum(int i){int v=0;for(;~i;(i&=i+1)--) v+=c[i];return v;}
//Main
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
R(i,0,n){
int y,l,r; cin>>y>>l>>r;
if(r-l==M) ++ans;
d.pb(l),d.pb(r),a.pb(segment(0,y,l,r));
}
R(i,0,m){
int x,l,r; cin>>x>>l>>r;
if(r-l==M) ++ans;
d.pb(x),a.pb(segment(1,l,x,1)),a.pb(segment(1,r,x,-1));
}
sort(be(a),en(a),[&](segment p,segment q){
if(p.y!=q.y) return p.y<q.y;
return p.op*p.r>q.op*q.r;
});
sort(be(d),en(d)),d.erase(unique(be(d),en(d)),en(d));
c.assign(sz(d),0);
// c.assign(M+1,0);
for(auto u:a){
if(u.op){
int i=lower_bound(be(d),en(d),u.l)-be(d);
add(i,u.r);
} else {
int l=lower_bound(be(d),en(d),u.l)-be(d);
int r=lower_bound(be(d),en(d),u.r)-be(d);
ans+=sum(r)-sum(l-1);
}
}
cout<<ans<<'
';
return 0;
}
祝大家学习愉快！