调了好几天……终于调出来了……（连我这么懒的人都来写博客了，可见……）
第一眼看这道题，这不排序线段树吗？橙题级别？嗯嗯？
是那不经意的回眸，我看见了你，数据范围。
1e9……
显然，直接开线段树是不可能的，空间不够，时间也不够。
那么肯定是要离散化的——离散化线段树。
比如：我们要修改【1000，8000】，【2000，9000】，那么我们只要一一离散化：
1——>1000
2——>2000
3——>8000
4——>9000
那么只要修改【1，3】，【2，4】就可以了。
于是我就快乐地写了代码，发现样例都过不去……di了半天才发现一个问题：如果我要跨区间修改，并且要修改的L，R是最后一层，也就是说，我们要单点修改L，R的时候，这两个区间的长度都是1，那么答案贡献就是2*x，但是需要修改的贡献是 ( p [ R ] - p [ L ] + 1 ) * x，这不对啊……
最后发现，只要把区间设为左闭右开，那么就不会出现上述问题，因为这个时候相邻的两个区间分别的R，L是同一个数。就是 【1，2），【2，3）。在这之后直接线段树就可以了，但是要注意建树，sum的修改，边界的判断都要改一改，因为区间定义的变化。
终于体会到了题里的 “ 区间的修改为左开右闭 ” 是什么意思了……原来是这样！
代码 time ——
#include<cstdio> #include<iostream> #include<cstring> #include<queue> #include<algorithm> using namespace std; #define maxn 80000*4 #define ls now<<1 #define rs now<<1|1 #define int long long struct node { int L,R,H; } q[maxn]; int l[maxn],r[maxn],p[maxn],sum[maxn],lazy[maxn]; int n,tot,T; bool cmp(node a,node b) { return a.H<b.H; } void build(int L,int R,int now) { l[now]=L; r[now]=R; if(L==R-1) return ; int mid=(L+R)>>1; build(L,mid,ls); build(mid,R,rs); } int find(int x) { int L=1,R=T; while(L<=R) { int mid=(L+R)>>1; if(p[mid]==x) return mid; if(p[mid]<x) L=mid+1; else R=mid-1; } return 0; } void pushdown(int now) { if(!lazy[now]) return ; lazy[ls]=lazy[rs]=lazy[now]; sum[ls]=lazy[now]*(p[r[ls]]-p[l[ls]]); sum[rs]=lazy[now]*(p[r[rs]]-p[l[rs]]); lazy[now]=0; return ; } void up(int now) { sum[now]=sum[ls]+sum[rs]; } void update(int now,int L,int R,int x) { if(L==l[now]&&R==r[now]) { lazy[now]=x; sum[now]=x*(p[R]-p[L]); return ; } pushdown(now); int mid=(l[now]+r[now])>>1; if(R<=mid) update(ls,L,R,x); else if(L>=mid) update(rs,L,R,x); else { update(ls,L,mid,x); update(rs,mid,R,x); } up(now); } main() { scanf("%lld",&n); for(int i=1; i<=n; i++) { scanf("%lld%lld%lld",&q[i].L,&q[i].R,&q[i].H); p[++tot]=q[i].L; p[++tot]=q[i].R; } sort(q+1,q+n+1,cmp); sort(p+1,p+tot+1); T=unique(p+1,p+tot+1)-p-1; build(1,T,1); for(int i=1; i<=n; i++) { int L=find(q[i].L); int R=find(q[i].R); update(1,L,R,q[i].H); } printf("%lld ",sum[1]); return 0; }