POJ最近做过的原题。
/*
ID: cuizhe
LANG: C++
TASK: picture
*/
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
using namespace std;
#define maxn 10000
#define lson l , m, rt<<1
#define rson m+1, r,rt<<1|1
int que[maxn*];
int sum[maxn*];
int cnt[maxn*];
bool lbd[maxn*] , rbd[maxn*];
int numseg[maxn*];
struct node
{
int lx,rx,y;
int s;
node() {}
node(int a,int b,int c,int d):lx(a),rx(b),y(c),s(d) {}
bool operator < (const node &S) const
{
if(y == S.y) return s > S.s;
return y < S.y;
}
} mat[maxn];
int bin(int x,int n)
{
int str,end,mid;
str = ,end = n;
while(str <= end)
{
mid = (str+end)/;
if(que[mid] == x)
return mid;
else if(que[mid] > x)
end = mid - ;
else
str = mid + ;
}
return mid;
}
void pushup(int rt,int l,int r)
{
if(cnt[rt])
{
lbd[rt] = rbd[rt] = ;
sum[rt] = que[r+] - que[l];
numseg[rt] = ;
}
else if (l == r)
{
sum[rt] = numseg[rt] = lbd[rt] = rbd[rt] = ;
}
else
{
lbd[rt] = lbd[rt<<];
rbd[rt] = rbd[rt<<|];
sum[rt] = sum[rt<<] + sum[rt<<|];
numseg[rt] = numseg[rt<<] + numseg[rt<<|];
if (lbd[rt<<|] && rbd[rt<<]) numseg[rt] -= ;
}
}
void update(int L,int R,int c,int l,int r,int rt)
{
if(L <= l&&r <= R)
{
cnt[rt] += c;
pushup(rt,l,r);
return ;
}
int m = (l+r)>>;
if(L <= m)
update(L,R,c,lson);
if(R > m)
update(L,R,c,rson);
pushup(rt,l,r);
}
int main()
{
int n,num,i,l,r;
int a,b,c,d;
freopen("picture.in","r",stdin);
freopen("picture.out","w",stdout);
while(scanf("%d",&n)!=EOF)
{
if(!n) break;
num = ;
for(i = ; i < n; i ++)
{
scanf("%d%d%d%d",&a,&b,&c,&d);
que[num] = a;
mat[num ++] = node(a,c,b,);
que[num] = c;
mat[num ++] = node(a,c,d,-);
}
sort(que,que+num);
sort(mat,mat+num);
int k = ;
for(i = ; i < num; i ++)
{
if(que[i] != que[i-])
que[k++] = que[i];
}
int ans = ,last = ;
memset(cnt,,sizeof(cnt));
memset(sum,,sizeof(sum));
memset(lbd,,sizeof(lbd));
memset(rbd,,sizeof(rbd));
for(i = ; i < num; i ++)
{
l = bin(mat[i].lx,k-);
r = bin(mat[i].rx,k-)-;
if(l <= r)
update(l,r,mat[i].s,,k-,);
ans += numseg[] * (mat[i+].y - mat[i].y);
ans += abs(sum[] - last);
last = sum[];
}
printf("%d\n",ans);
}
return ;
}