DCrusher有一个数列,初始值均为0,他进行N次操作,每次将数列[a,b)这个区间中所有比k小的数改为k,他想知
道N次操作后数列中所有元素的和。他还要玩其他游戏,所以这个问题留给你解决。
Input
第一行一个整数N,然后有N行,每行三个正整数a、b、k。
N<=40000 , a、b、k<=10^9
Output
一个数,数列中所有元素的和
Sample Input
4
2 5 1
9 10 4
6 8 2
4 6 3
Sample Output
16
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; int n,xx,yy,zz,root,cnt,inf=1000000000,tree[22222222],lson[22222222],rson[22222222]; long long ans; void insert(int l,int r,int &pos,int L,int R,int Wei) { if(!pos) pos=++cnt; if(l>=L&&r<=R) { tree[pos]=max(tree[pos],Wei); return; } int mid=(l+r)>>1; if(mid<L) insert(mid+1,r,rson[pos],L,R,Wei); else if(mid>=R) insert(l,mid,lson[pos],L,R,Wei); else insert(l,mid,lson[pos],L,R,Wei),insert(mid+1,r,rson[pos],L,R,Wei); } void dfs(int l,int r,int x,int Wei) { if(!x) { ans+=(r-l+1)*Wei; return; } int mid=(l+r)>>1; dfs(l,mid,lson[x],max(Wei,tree[lson[x]])); dfs(mid+1,r,rson[x],max(Wei,tree[rson[x]])); } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%d%d",&xx,&yy,&zz); if(xx==yy)continue;//特殊情况,讨论一下 insert(1,inf,root,xx,yy-1,zz); } dfs(1,inf,root,0); printf("%lld\n",ans); }