类似求面积并。。2Y。。
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
using namespace std;
#define LL __int64
#define maxn 40100
#define lson l , m, rt<<1
#define rson m+1, r,rt<<1|1
int que[maxn*];
int sum[maxn*];
int cnt[maxn*];
struct node
{
int x,y,s;
node(){}
node(int a,int b,int c):x(a),y(b),s(c){}
bool operator < (const node &S)const
{
return x < S.x;
}
}mat[maxn*];
int bin(int x,int n)
{
int str,mid,end;
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])
{
sum[rt] = que[r+] - que[l];
}
else if(l == r)
sum[rt] = ;
else
sum[rt] = sum[rt<<] + sum[rt<<|];
}
void update(int L,int R,int c,int l,int r,int rt)
{
int m;
if(l >= L&&r <= R)
{
cnt[rt] += c;
pushup(rt,l,r);
return ;
}
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,a,b,c,i,k,num,l,r;
while(scanf("%d",&n)!=EOF)
{
memset(cnt,,sizeof(cnt));
memset(sum,,sizeof(sum));
num = ;
for(i = ;i < n;i ++)
{
scanf("%d%d%d",&a,&b,&c);
que[num] = ;
mat[num++] = node(a,c,);
que[num] = c;
mat[num++] = node(b,c,-);
}
sort(mat,mat+num);
sort(que,que+num);
k = ;
for(i = ;i < num;i ++)
{
if(que[k] != que[i])
que[k++] = que[i];
}
LL ans = ;
for(i = ;i < num-;i ++)
{
l = ;
r = bin(mat[i].y,k-)-;
if(l <= r)
update(l,r,mat[i].s,,k-,);
ans = ans + (LL)sum[]*(mat[i+].x - mat[i].x);
}
printf("%I64d\n",ans);
}
return ;
}