本文主要是介绍BNU 49100超级线段树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
超级线段树
5000ms
65536KB
64-bit integer IO format: %lld Java class name: Main
Font Size:
whalyzh是一个数据结构弱渣，于是他决定恶补一下。众所周知，线段树可以实现对一个[L,R]区间进行一些操作，比如加上一个数或者求最值等等……一天，whalyzh遇到一道题，需要对一个序列进行M次区间操作，由于操作的种类很多，做着做着whalyzh就晕了。现在，他只想知道M次操作后序列中每个数最后一次被执行的操作是什么？
Input
输入数据有多组。
第一行输入一个整数T(T≤10)，表示数据组数。
每组数据第一行为两个整数N(N≤10^6)、M(M≤10^6)，分别代表序列长度和操作次数。
接下来M行每行三个整数L、R、P(1≤L≤R≤N, 1≤P≤10^6)，代表对区间[L,R]执行了操作P。
Output
每组数据输出N行，第i行输出表示序列第i个数最后执行的操作，如果没有执行过操作输出0。
Sample Input
1 3 2 1 2 1 1 1 2
Sample Output
2 1 0
Source
第十三届北京师范大学程序设计竞赛决赛
Author
hwq
#include<stdio.h>
#include<string.h>
const int N = 1000005;
int flag[N*3];
void build(){memset(flag,0,sizeof(flag));
}
void pushUp(int k){if(flag[k]){if(flag[k<<1]==0)flag[k<<1]=flag[k];if(flag[k<<1|1]==0)flag[k<<1|1]=flag[k];flag[k]=0;}
}
void updata(int l,int r,int k,const int& L, const int& R,const int& op){if(flag[k])return ;if(L<=l&&r<=R){flag[k]=op; return ;}pushUp(k);int mid=(l+r)>>1;if(L<=mid)updata(l,mid,k<<1,L,R,op);if(mid<R)updata(mid+1,r,k<<1|1,L,R,op);if(flag[k<<1]==flag[k<<1|1])flag[k]=flag[k<<1];
}
void query(int l,int r,int k){if(l==r){printf("%d\n",flag[k]); return ;}pushUp(k);int mid=(l+r)>>1;query(l,mid,k<<1);query(mid+1,r,k<<1|1);
}
struct EDG
{int a,b,op;
}edg[N];
int main(){int T,n,m,a,b,op;scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);build();for(int i=1;i<=m;i++){scanf("%d%d%d",&edg[i].a,&edg[i].b,&edg[i].op);}for(int i=m;i>0;i--){updata(1,n,1,edg[i].a,edg[i].b,edg[i].op);}query(1,n,1);}
}
这篇关于BNU 49100超级线段树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
