bzoj4363 蒟蒻的数列

bzoj4363 蒟蒻的数列

​​ Description 蒟蒻DCrusher不仅喜欢玩扑克，还喜欢研究数列 题目描述 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 线段树离散化 因为我们范围是1e9 所以就算是动态加点线段树也是超时 所以我们考虑类似扫描线的方法 设每个叶子节点表示一个左闭右开的区间 然后我们先马上离散化 然后建树的时候题目为了方便我们所以给了个左开右闭 然后记得插入的时候右端点要－1 仔细想想x

#include#include#define N 44000using namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=gc();} while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=gc();} return x*f;}struct node{ int x,y,z;}q[N];int queue[N<<1],num,n,top,root;struct node1{ int l,r,left,right,max;}tree[N<<3];inline void build(int &x,int l,int r){ x=++num;tree[x].l=l;tree[x].r=r; if (l==r)return; int mid=l+r>>1; build(tree[x].left,l,mid);build(tree[x].right,mid+1,r);}inline bool cmp(node a,node b){return a.z=tree[x].r){tree[x].max=v;return;} int mid=tree[x].l+tree[x].r>>1; if (l<=mid) insert1(tree[x].left,l,r,v); if (r>mid) insert1(tree[x].right,l,r,v);}long long query(int x,int l,int r){ if (l<=tree[x].l&&r>=tree[x].r) return tree[x].max; int mid=tree[x].l+tree[x].r>>1; if (l<=mid) {tree[tree[x].left].max=max(tree[tree[x].left].max,tree[x].max);return query(tree[x].left,l,r);}else {tree[tree[x].right].max=max(tree[tree[x].right].max,tree[x].max);return query(tree[x].right,l,r);}}void print(int x){ if (tree[x].left) print(tree[x].left); printf("%d %d %d\n",tree[x].l,tree[x].r,tree[x].max); if (tree[x].right) print(tree[x].right);}int main(){ freopen("bzoj4636.in","r",stdin); n=read(); for (int i=1;i<=n;++i){q[i].x=read();q[i].y=read();q[i].z=read();queue[++top]=q[i].x;queue[++top]=q[i].y;} sort(q+1,q+n+1,cmp);sort(queue+1,queue+top+1);int nn=unique(queue+1,queue+top+1)-queue-1; //for (int i=1;i<=nn;++i) printf("%d,queue[i]); build(root,1,nn-1); //for (int i=1;i<=n;++i) printf("%d %d %d\n",q[i].x,q[i].y,q[i].z); for (int i=1;i<=n;++i) insert1(root,lower_bound(queue+1,queue+nn+1,q[i].x)-queue,lower_bound(queue+1,queue+nn+1,q[i].y)-queue-1,q[i].z);long long ans=0;// print(root); for (int i=1;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。