HDU 1542(矩形面积并） - c++编程基础

sert(3,4,1);
t.print();
t.insert(2,3,-1);
t.print();

*/

double ans=0;a[0].h=a[1].h;
for (int i=1;i<=2*n;i++)
{
ans+=(a[i].h-a[i-1].h)*t.sum[1];
t.insert(hpos[a[i].x1]+1,hpos[a[i].x2],a[i].type);
/* t.print();
cout< cout< cout< */ }
printf("Test case #%d\nTotal explored area: %.2lf\n\n",tt,ans);

}
return 0;
}

上述程序效率较慢(m(logm)^2) ,m为边数

我们考虑到，每次上传实在太耗时了。
仔细观察方程，发现每次修改的点一定是从叶结点到根节点的路上的结点的兄弟（不包括路上）
因此每次被影响的一定是路上的结点。
故我们每次只更新结点的值，最后直接由根节点向上递归，得到程序2-效率为O(mlogm) ：

[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define MAXN (2000+10)
#define MAXT (1000*2*10)
#define Lson (x<<1)
#define Rson ((x<<1)^1)
int tt,n,size;
double x[MAXN];
struct SegMent
{
double x1,x2,h;
int type;
SegMent(){}
SegMent(double _x1,double _x2,double _h,int _type):x1(_x1),x2(_x2),h(_h),type(_type){}
friend bool operator<(const SegMent a,const SegMent b){return a.h }a[MAXN];
map hpos;
double len[MAXT];
struct SegMentTree
{
int n,M,cnt[MAXT];
double sum[MAXT];
int mark[MAXT];
void fillchar(int _n)
{
n=_n;
memset(cnt,0,sizeof(cnt));
memset(sum,0,sizeof(sum));
memset(mark,0,sizeof(mark));
M=1;while (M-2 x[0]=0;memset(len,0.0,sizeof(len));
for (int i=M+1;i<=M+size;i++) len[i]=x[i-M]-x[i-M-1];
for (int i=M-1;i>0;i--) len[i]=len[i<<1]+len[(i<<1)^1];
}
void pushup(int x)
{
sum[x]=cnt[x] len[x]:(x>=M 0:sum[Lson]+sum[Rson]);
}
void update(int x)
{
for (;x;x>>=1)
{
pushup(x);
}
}

void insert(int l,int r,int c)
{
int ll=l-1+M,rr=r+1+M;
for (l=l-1+M,r=r+1+M;l^r^1;l>>=1,r>>=1)
{
if (~l&1) {cnt[l+1]+=c;pushup(l+1);} /*改变sum的值 */
if (r&1) {cnt[r-1]+=c;pushup(r-1);}
}
update(ll);update(rr);
}
}t;

int main()
{
// freopen("Hdu1542.in","r",stdin);
tt=0;
while (scanf("%d",&n)!=EOF)
{
tt++;
if (!n) break;
for (int i=1;i<=2*n;i+=2)
{
double x1,y1,x2,y2;
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
x[i]=x1;x[i+1]=x2;
a[i]=SegMent(x1,x2,y1,1);
a[i+1]=SegMent(x1,x2,y2,-1);
}

sort(a+1,a+2*n+1);
sort(x+1,x+2*n+1);
size=unique(x+1,x+2*n+1)-(x+1);
for (int i=1;i<=size;i++) hpos[x[i]]=i;
t.fillchar(size);

double ans=0;a[0].h=a[1].h;
for (int i=1;i<=2*n;i++)
{
ans+=(a[i].h-a[i-1].h)*t.sum[1];
t.insert(hpos[a[i].x1]+1,hpos[a[i].x2],a[i].type);
}
printf("Test case #%d\nTotal explored area: %.2lf\n\n",tt,ans);

}
return 0;
}

HDU 1542(矩形面积并）(二)