【HDU4052】【ZOJ3540】Adding New Machine 线段树+扫描线
题意:W*H的格子上放着一些旧机器,现在要往图上放1*M的新机器,问放机器的方式有多少种 做法:把每个旧机器的范围扩展一下,向左&向下扩展m-1个格子,这样就转化为了求矩阵面积并的问题。同时要把矩形位置坐标转化为线的坐标。 注意考虑long long…#include<bits/stdc++.h>#define mid int m = (l+r)>>1;#define lson l, m,