线段树90pts求调

P1253 扶苏的问题

ZVitality @ 2023-03-20 22:13:29

rt,WA on #10。

#include <bits/stdc++.h>
using namespace std;

#define int long long

inline int Read() {
  int x = 0 , f = 1;
  char c = getchar();
  for( ; c < '0' || c > '9' ; c = getchar() ) f ^= ( c == '-' );
  for( ; c >= '0' && c <= '9' ; c = getchar() ) x = ( x << 3 ) + ( x << 1 ) + ( c ^ 48 );
  return f ? x : -x;
}

const int _ = 1e6 + 5 , NONE = -1145141919810;
int n , q;

int a[_] , covertag[_*4] , addtag[_*4] , tree[_*4];

void PushUp( int p ) { tree[ p ] = max( tree[ p * 2 ] , tree[ p * 2 + 1 ] ) ; }

void CoverDown( int p ) {
  if( covertag[ p ] != NONE ) {
    addtag[ p * 2 ] = addtag[ p * 2 + 1 ] = 0;
    tree[ p * 2 ] = tree[ p * 2 + 1 ] = covertag[ p ];
    covertag[ p * 2 ] = covertag[ p * 2 + 1 ] = covertag[ p ];
    covertag[ p ] = NONE;
  }
}

void AddDown( int p ) {
  if( addtag[ p ] ) {
    CoverDown( p );
    tree[ p * 2 ] += addtag[ p ] , tree[ p * 2 + 1 ] += addtag[ p ];
    addtag[ p * 2 ] += addtag[ p ] , addtag[ p * 2 + 1 ] += addtag[ p ];
    addtag[ p ] = 0;
  }
}

void PushDown( int p ) {
  CoverDown( p ) , AddDown( p ); 
}

void BuildTree( int a[] , int l , int r , int p ) {
  if( l == r ) {
    tree[ p ] = a[ l ];
    covertag[ p ] = NONE;
    return;
  }
  int mid = ( l + r ) / 2;
  BuildTree( a , l , mid , p * 2 ) , BuildTree( a , mid + 1 , r , p * 2 + 1 );
  PushUp( p );
}

void Add( int l , int r , int x , int y , int val , int p ) {
  if( x <= l && r <= y ) {
    CoverDown( p );
    tree[ p ] += val;
    addtag[ p ] += val;
    return;
  }
  PushDown( p );
  int mid = ( l + r ) / 2;
  if( x <= mid ) Add( l , mid , x , y , val , p * 2 );
  if( y > mid ) Add( mid + 1 , r , x , y , val , p * 2 + 1 );
  PushUp( p );
}

void Bulldozing( int l , int r , int x , int y , int val , int p ) {
  if( x <= l && r <= y ) {
    tree[ p ] = val;
    addtag[ p ] = 0;
    covertag[ p ] = val;
    return;
  }
  PushDown( p );
  int mid = ( l + r ) / 2;
  if( x <= mid ) Bulldozing( l , mid , x , y , val , p * 2 );
  if( y > mid ) Bulldozing( mid + 1 , r , x , y , val , p * 2 + 1 );
  PushUp( p );
}

int GetMax( int l , int r , int x , int y , int p ) {
  if( x <= l && r <= y ) return tree[ p ];
  PushDown( p );
  int mid = ( l + r ) / 2 , ans = -1000000000000000;
  if( x <= mid ) ans = GetMax( l , mid , x , y , p * 2 );
  if( y > mid ) ans = max( ans , GetMax( mid + 1 , r , x , y , p * 2 + 1 ) );
  return ans;
}

signed main() {
  cin >> n >> q;
  for( int i = 1 ; i <= n ; i++ ) a[ i ] = Read();
  for( int i = 1 ; i <= 4 * n ; i++ ) covertag[ i ] = NONE;
  BuildTree( a , 1 , n , 1 );
  while( q-- ) {
    int op = Read() , l = Read() , r = Read() , x;
    if( op == 1 ) x = Read() , Bulldozing( 1 , n , l , r , x , 1 );
    if( op == 2 ) x = Read() , Add( 1 , n , l , r , x , 1 );
    if( op == 3 ) printf( "%lld\n" , GetMax( 1 , n , l , r , 1 ) );
  }
  return 0;
}

by ZVitality @ 2023-03-20 22:14:15

错误信息:

wrong answer On line 16226 column 1, read 2, expected 5.


by ZVitality @ 2023-03-20 22:14:47

发现问题记得 @ 我。


by ZVitality @ 2023-03-21 13:01:18

破解了,add时不要coverdown就好了,此贴完结。


|