CF - Div2 - 207 - C 문제 + 선분 트 리
구간 업데이트
/*
+ +
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
c = %d
",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
",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("
");
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.