简单线段树。。。
区间更新
/*
线段树+修改区间+询问区间
update是把某个区间ab的数改为c
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include<map>
#include<math.h>
typedef long long ll;
//typedef __int64 int64;
const int maxn = 300005;
const int maxm = 1005;
const int inf = 0x7FFFFFFF;
const double pi = acos(-1.0);
const double eps = 1e-8;
using namespace std;
#define LEFT( x ) (x<<1)
#define RIGHT( x ) ((x<<1)+1)
struct node{
int l,r,win;
int flag;
}tree[ maxn<<2 ];
struct QQ{
int x,y;
int win;
}a[ maxn ];
void pushdown( int n ){
if( tree[ n ].flag!=0 ){
tree[ LEFT( n ) ].flag = tree[ RIGHT( n ) ].flag = tree[ n ].flag;
tree[ LEFT( n ) ].win = tree[ n ].win;//tree[ n ].flag*((m+1)/2);
tree[ RIGHT( n ) ].win = tree[ n ].win;//tree[ n ].flag*( m-(m+1)/2 );
tree[ n ].flag = 0;
}
return;
}
void build( int l,int r,int n ){
if( l==r ){
tree[ n ].win = 0;
tree[ n ].flag = 0;
tree[ n ].l=tree[ n ].r = l;
return ;
}
tree[ n ].win = 0;
tree[ n ].flag = 0;
tree[ n ].l = l;
tree[ n ].r = r;
int mid;
mid = (l+r)>>1;
build( l,mid,LEFT( n ) );
build( mid+1,r,RIGHT( n ) );
return;
}
void update( int a,int b,int c,int l,int r,int n ){
if( a==l&&b==r ){
tree[ n ].flag = 1;
tree[ n ].win = c;
//printf("l = %d,r = %d\nc = %d\n",l,r,c);
return ;
}
pushdown( n );
int mid;
mid = (l+r)>>1;
if( mid>=b ) update( a,b,c,l,mid,LEFT( n ) );
else if( mid<a ) update( a,b,c,mid+1,r,RIGHT( n ));
else {
update( a,mid,c,l,mid,LEFT( n ) );
update( mid+1,b,c,mid+1,r,RIGHT( n ) );
}
return ;
}
int query( int a,int b,int l,int r,int n ){
if( a==l&&b==r ){
//printf("l = %d, r = %d,c = %d\n",l,r,tree[n].win);
return tree[ n ].win;
}
pushdown( n );
int mid;
mid = (l+r)>>1;
if( mid>=b ) return query( a,b,l,mid,LEFT( n ) );
else if( mid<a ) return query( a,b,mid+1,r,RIGHT( n ));
else return query( a,mid,l,mid,LEFT( n ) )+query( mid+1,b,mid+1,r,RIGHT( n ));
}
int main(){
int n,m;
while( scanf("%d%d",&n,&m)==2 ){
for( int i=1;i<=m;i++ ){
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].win);
}
build( 1,n,1 );
for( int i=m;i>=1;i-- ){
if( a[i].win-1>=a[i].x ) update( a[i].x,a[i].win-1,a[i].win,1,n,1 );
if( a[i].y>=a[i].win+1 )update( a[i].win+1,a[i].y,a[i].win,1,n,1 );
}
int f = -1;
for( int i=1;i<=n;i++ ){
int ans = query( i,i,1,n,1 );
if( ans==i ) {
if(f==-1)printf("0"),f++;
else printf(" 0");
}
else {
if( f==-1 ) printf("%d",ans),f++;
else printf(" %d",ans);
}
}
printf("\n");
}
return 0;
}
分享到:
相关推荐
COMFAST品牌 CF-WU710N V2型号 USB无线网卡 驱动 亲测能用
七彩虹 CF-P8 MX 2.4A bios
CF-926AC.zip
七彩虹主板 cf-af3-e v18 主板BIOS
松下touchbook gps驱动程序注册表,电脑型号CF-H2
松下Panasonic 笔记本CF-N8 -N9 -N10 -S8 -S9 -S10等系列 圆形选装触摸板驱动,内涵两个程序都装上即可使用。
2.将您的nexus 5调整到bootloader模式,具体的办法是先关机,然后在关机的状态下,同时按住电源和音量下键。 3.通过USB将nexus 5和电脑相连接。 4.下载nexus 5对应的CF-Auto-Root版本 节约您的时间,下载地址呈上...
安装方法: 1、必须要有有线网卡能上网,因为安装的时候,它要下载字库什么的...2、解压双击install.pkg按提示安装即可,超级简单,如果成功了后,在任务栏上,就有wifi信号了。现在发文件,就是用无线发送的,很nice的
七彩虹cf-p8 mx 2.4a bios 测试可以正常使用
Linux系统下的rtl8188eu驱动程序,适合COMFAST CF-WU810N驱动(附安装说明)
CF-A7-MX C.A780T D3 V19
内附无线网卡Comfast CF-WU810N的Linux驱动版本及安装说明。解压后根据《安装说明.txt》的步骤执行即可完成无线网卡的linux驱动安装。
论文研究-以特征函数为传递参数的CF-GERT及其矩阵法求解.pdf, 本文构建了以特征函数和传递概率为传递函数的CF-GERT(characteristic function based GERT)模型,利用...
松下CF-T7触摸屏驱动 松下CF-T7触摸屏驱动
CF-E218N固件(2013-10)
I1CF-M1202C-C2S2台信透明标签传感器说明书.docx
panasonic cf-p1 说明书
QCA953x-CF-E320编程器固件
分光测色计 CF-300
CF-150NS 驱动 无线 ap 无线网络