二分写错了血T。。。。。
线段树标记永久化。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxn 200050 using namespace std; struct move { int l,r,p; }mov[maxn]; int n,root,tot=0,a[maxn],cnt=0,x,y,z,len; int ls[maxn<<2],rs[maxn<<2],mx[maxn<<2]; long long ans=0; void build(int &now,int left,int right) { now=++tot;mx[now]=0; if (left==right) return; int mid=(left+right)>>1; build(ls[now],left,mid); build(rs[now],mid+1,right); } int find(int x) { int l=1,r=len; while (l<=r) { int mid=(l+r)>>1; if (x==a[mid]) return mid; else if (x<a[mid]) r=mid-1; else l=mid+1; } return l; } void modify(int now,int left,int right,int l,int r,int p) { if ((left==l) && (right==r)) { mx[now]=max(mx[now],p); return; } int mid=(left+right)>>1; if (r<=mid) modify(ls[now],left,mid,l,r,p); else if (l>=mid+1) modify(rs[now],mid+1,right,l,r,p); else { modify(ls[now],left,mid,l,mid,p); modify(rs[now],mid+1,right,mid+1,r,p); } } int ask(int now,int left,int right,int pos) { if ((left==right) && (left==pos)) return mx[now]; int mid=(left+right)>>1; if (pos<=mid) return max(mx[now],ask(ls[now],left,mid,pos)); else return max(ask(rs[now],mid+1,right,pos),mx[now]); } int main() { scanf("%d",&n); for (int i=1;i<=n;i++) { scanf("%d%d%d",&x,&y,&z); mov[i].l=x;mov[i].r=y;mov[i].p=z; a[++cnt]=x;a[++cnt]=y; } sort(a+1,a+cnt+1); len=unique(a+1,a+cnt+1)-a-1; build(root,1,len); for (int i=1;i<=n;i++) { if (mov[i].l==mov[i].r) continue; modify(root,1,len,find(mov[i].l),find(mov[i].r)-1,mov[i].p); } for (int i=1;i<=len-1;i++) ans+=(long long)ask(root,1,len,i)*(a[i+1]-a[i]); printf("%lld ",ans); return 0; }