题意：
给出n个三元组 e[i]=（si，ti，wi）
第i个三元组的价值为 Σ w[j] ，j 满足以下4个条件：
1、j<i
2、tj<ti
3、sj<si
4、不存在j<k<i,且sj<sk<si
把每个三元组看作二维平面上的一个点（i，si）
先不考虑t，
那么j若满足要求，必须满足以（j，sj）为左下角，以（i，si）为右上角的矩形内没有其他的三元组
可以用CDQ分治解决
设三元组e[i]的坐标为（x，y）=（i，si）
先将所有的三元组按s排序，然后按x归并
即左右两边归并时，左边所有三元组的y小于右边所有三元组的s
归并结束后，左右两边合并为x递增的集合
考虑左边对右边的贡献
在归并的过程中维护两个单调栈l和r
栈l 维护左边的三元组，满足x单调递增，y单调递减
栈r 维护右边的三元组，满足x单调递增，y单调递增，且栈顶的y一定小于当前的y
对于右边的一个三元组j，左边对其有贡献的三元组i满足
1、i<j，因为是按x归并，所以此条件一定满足
2、i在栈l中，如果i不在栈l中，说明i后面，j前面存在一个k，满足si<sk<sj
3、设栈r的栈顶为k，i>k，否则这个k会使 i<k<j 且si<sk<sj
我们只维护栈l中三元组的信息，即可满足条件2
至于条件3，因为栈l的x单调递增，二分查找第一个满足条件的，那么它到栈l的栈顶都满足条件
记录栈l中w的前缀和即可解决
现在再考虑t，只需要将前缀和改为可持久化权值线段树即可
#include<cstdio> #include<iostream> #include<algorithm> using namespace std; #define N 50001 int n; struct node { int s,t,w; int id; int ans; }e[N],g[N],stl[N],str[N]; int has[N]; bool cmpy(node p,node q) { return p.s<q.s; } bool cmpx(node p,node q) { return p.id<q.id; } namespace Segment { int tot,rt_id; int root[N]; int sum[N*16],lc[N*16],rc[N*16]; void pre() { tot=rt_id=0; } int query(int x,int y,int l,int r,int opr) { if(r<=opr) return sum[y]-sum[x]; int mid=l+r>>1; int res=query(lc[x],lc[y],l,mid,opr); if(opr>mid) res+=query(rc[x],rc[y],mid+1,r,opr); return res; } int insert(int x,int l,int r,int pos,int w) { int num=++tot; sum[num]=sum[x]; lc[num]=lc[x]; rc[num]=rc[x]; sum[num]+=w; if(l==r) return num; int mid=l+r>>1; if(pos<=mid) lc[num]=insert(lc[x],l,mid,pos,w); else rc[num]=insert(rc[x],mid+1,r,pos,w); return num; } int get(int L,int R,int lim) { if(L>R || !lim) return 0; return query(root[L-1],root[R],1,n,lim); } void del() { tot=root[rt_id]-1; rt_id--; } void add(int pos,int w) { rt_id++; root[rt_id]=insert(root[rt_id-1],1,n,pos,w); } }; void read(int &x) { x=0; char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); } } void init() { read(n); for(int i=1;i<=n;++i) { read(e[i].s); read(e[i].t); read(e[i].w); e[i].id=i; } for(int i=1;i<=n;++i) has[i]=e[i].s; sort(has+1,has+n+1); for(int i=1;i<=n;++i) e[i].s=lower_bound(has+1,has+n+1,e[i].s)-has; for(int i=1;i<=n;++i) has[i]=e[i].t; sort(has+1,has+n+1); for(int i=1;i<=n;++i) e[i].t=lower_bound(has+1,has+n+1,e[i].t)-has; } void solve(int l,int r) { if(l==r) return; int mid=l+r>>1; solve(l,mid); solve(mid+1,r); int topl=0,topr=0; int i=l,j=mid+1,tmp=l; Segment::pre(); while(i<=mid || j<=r) { if(j<=r && ( i>mid || e[j].id<e[i].id)) { while(topr && str[topr].s>e[j].s) topr--; int pos=lower_bound(stl+1,stl+topl+1,str[topr],cmpx)-stl; e[j].ans+=Segment::get(pos,Segment::rt_id,e[j].t-1); str[++topr]=e[j]; g[tmp++]=e[j++]; } else { while(topl && stl[topl].s<e[i].s) { Segment::del(); topl--; } Segment::add(e[i].t,e[i].w); stl[++topl]=e[i]; g[tmp++]=e[i++]; } } for(int k=l;k<=r;++k) e[k]=g[k]; } int main() { freopen("rehearsal.in","r",stdin); freopen("rehearsal.out","w",stdout); init(); sort(e+1,e+n+1,cmpy); solve(1,n); sort(e+1,e+n+1,cmpx); for(int i=1;i<=n;++i) printf("%d ",e[i].ans); }