IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓ 		图片批量下载器
↓批量下载图片,美女图库↓ 		图片自动播放器
↓图片自动播放器↓ 		一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 【地狱副本】数据结构之线段树Ⅲ——区间最值/赋值/修改/历史值操作（HDU5306，Tyvj 1518，【清华集训2015】V，HDU6315，HDU1828，POJ3162） -> 正文阅读

[数据结构与算法]【地狱副本】数据结构之线段树Ⅲ——区间最值/赋值/修改/历史值操作（HDU5306，Tyvj 1518，【清华集训2015】V，HDU6315，HDU1828，POJ3162）

文章目录

Gorgeous Sequence

HDU5306

操作

  • 区间与 x x x取 m i n \rm min min
  • 查询区间最大值
  • 查询区间和

比较暴力的线段树维护区间

  • Max : 区间最大值
  • sub_max : 严格小于最大值的区间次大值
  • cnt_max : 最大值个数
  • sum : 区间和
  • tag : 区间取 m i n \rm min min的标记记录值

考虑取 m i n \rm min min操作走到一个区间上

  • 最大值都不大于取 m i n \rm min min的对象，说明操作没用，return

  • 如果小于最大值却严格大于次大值

    此时的操作相当于区间加，打标记 sum-=(Max-x)*max_cnt;Max=x

  • 否则暴力走两边

利用势能分析时间复杂度

  • 定义势能函数为 ∑ i d i \sum_i d_i ∑i?di?， i i i是线段树上的节点， d i d_i di?是这个节点对应的区间中，互不相同的元素个数
  • 初始时，显然势能是 O ( n l o g n ) O(\rm nlogn) O(nlogn)
  • 暴力对长度为 n n n的区间做 m i n \rm min min，消耗的时间是 O ( n ) O(n) O(n)，势能也会减少 O ( n ) O(n) O(n)
#include <cstdio>
#include <iostream>
using namespace std;
#define int long long
#define maxn 1000005
#define lson num << 1
#define rson num << 1 | 1
struct node {
	int Max, sub_max, cnt_max, sum, tag;
}t[maxn << 2];
int a[maxn];

void pushup( int num ) {
	if( t[lson].Max > t[rson].Max ) {
		t[num].Max = t[lson].Max;
		t[num].cnt_max = t[lson].cnt_max;
		t[num].sub_max = max( t[lson].sub_max, t[rson].Max );
	}
	else if( t[lson].Max < t[rson].Max ) {
		t[num].Max = t[rson].Max;
		t[num].cnt_max = t[rson].cnt_max;
		t[num].sub_max = max( t[rson].sub_max, t[lson].Max );
	}
	else {
		t[num].Max = t[lson].Max;
		t[num].cnt_max = t[lson].cnt_max + t[rson].cnt_max;
		t[num].sub_max = max( t[lson].sub_max, t[rson].sub_max );
	}
	t[num].sum = t[lson].sum + t[rson].sum;
}

void build( int num, int l, int r ) {
	t[num].Max = t[num].sub_max = t[num].cnt_max = t[num].sum = 0, t[num].tag = -1;
	if( l == r ) {
		t[num].Max = t[num].sum = a[l];
		t[num].sub_max = -1;
		t[num].cnt_max = 1;
		return;
	}
	int mid = l + r >> 1;
	build( lson, l, mid );
	build( rson, mid + 1, r );
	pushup( num );
}

void pushdown( int num ) {
	if( ! ~ t[num].tag ) return;
	int val = t[num].tag;
	if( t[lson].Max > val ) {
		t[lson].sum -= ( t[lson].Max - val ) * t[lson].cnt_max;
		t[lson].Max = t[lson].tag = val;
	}
	if( t[rson].Max > val ) {
		t[rson].sum -= ( t[rson].Max - val ) * t[rson].cnt_max;
		t[rson].Max = t[rson].tag = val;
	}
	t[num].tag = -1;
}

void modify( int num, int l, int r, int L, int R, int val ) {
	if( R < l or r < L or t[num].Max <= val ) return;
	if( L <= l and r <= R and t[num].sub_max < val ) {
		t[num].sum -= ( t[num].Max - val ) * t[num].cnt_max;
		t[num].Max = t[num].tag = val;
		return;
	}
	pushdown( num );
	int mid = l + r >> 1;
	modify( lson, l, mid, L, R, val );
	modify( rson, mid + 1, r, L, R, val );
	pushup( num );
}

int query_max( int num, int l, int r, int L, int R ) {
	if( r < L or R < l ) return -1;
	if( L <= l and r <= R ) return t[num].Max;
	pushdown( num );
	int mid = l + r >> 1;
	return max( query_max( lson, l, mid, L, R ), query_max( rson, mid + 1, r, L, R ) );
}

int query_sum( int num, int l, int r, int L, int R ) {
	if( r < L or R < l ) return 0;
	if( L <= l and r <= R ) return t[num].sum;
	pushdown( num );
	int mid = l + r >> 1;
	return query_sum( lson, l, mid, L, R ) + query_sum( rson, mid + 1, r, L, R );
}

signed main() {
	int n, m, T, opt, l, r, x;
	scanf( "%lld", &T );
	while( T -- ) {
		scanf( "%lld %lld", &n, &m );
		for( int i = 1;i <= n;i ++ ) scanf( "%lld", &a[i] );
		build( 1, 1, n );
		while( m -- ) {
			scanf( "%lld %lld %lld", &opt, &l, &r );
			switch ( opt ) {
				case 0 : { scanf( "%lld", &x ); modify( 1, 1, n, l, r, x );break; }
				case 1 : { printf( "%lld\n", query_max( 1, 1, n, l, r ) ); break; }
				case 2 : { printf( "%lld\n", query_sum( 1, 1, n, l, r ) ); break; }
			}
		}
	}
	return 0;
}

Tyvj 1518 CPU监控

BZOJ3064

操作

  • 区间加
  • 区间赋值
  • 查询区间最大值
  • 查询区间历史最大值

线段树维护

  • Max : 区间最大值
  • Hmax : 区间历史最大值
  • add : 区间加标记
  • Hadd : 区间历史最大加标记
  • tag : 区间赋值标记
  • Htag : 区间历史最大赋值标记

假想不合并标记，每个节点上有一个队列（按照时间先进先出），放着所有曾经推过来的标记

下推标记时，将该节点上所有的标记推到两个儿子处，并清空队列

对于每个节点，每次有一个区间加add标记推来时，令Max←Max+add 然后Hmax←max(Hmax,Max)

设推来的加法标记分别为 a d d [ 1... k ] add[1...k] add[1...k]，其前缀和为 S [ 1... k ] S[1...k] S[1...k]

则打上第 i i i个标记之后，Max的值为Max+S[i]

所以，Hmax的值为 max ? i = 1 k M a x + S [ i ] = M a x + max ? i = 1 k S [ i ] \max_{i=1}^k Max+S[i]=Max+\max_{i=1}^k S[i] maxi=1k?Max+S[i]=Max+maxi=1k?S[i]

因此只需记录 max ? i = 1 k S [ i ] \max_{i=1}^k S[i] maxi=1k?S[i]，就能得知该标记队列对节点的影响

合并加法标记时简单求和，前 i i i个标记合并后恰好等于 S [ i ] S[i] S[i]，那么 max ? i = 1 k S [ i ] \max_{i=1}^k S[i] maxi=1k?S[i]可以表述为标记的历史最大值Hadd

此题含有赋值操作，赋值操作优先级更高，做法略有不同

赋值一次相当于前面所有的加标记和当前最大值都会被改变

所以赋值的时候，先下放所有的加标记，然后清空（包括历史）

同时，在加标记的时候如果已经有了赋值标记，直接把加标记叠加在赋值标记上

同时记录赋值历史的最大值，其很有可能成为历史最大值

#include <cstdio>
#include <iostream>
using namespace std;
#define inf 1e18
#define maxn 100005
#define int long long
#define lson num << 1
#define rson num << 1 | 1
struct node {
	int Max, Hmax, add, Hadd, tag, Htag;
}t[maxn << 2];
int a[maxn];

void build( int num, int l, int r ) {
	t[num].Max = t[num].Hmax = t[num].tag = t[num].Htag = -inf;
	t[num].add = t[num].Hadd = 0;
	if( l == r ) { t[num].Max = t[num].Hmax = a[l]; return; }
	int mid = ( l + r ) >> 1;
	build( lson, l, mid );
	build( rson, mid + 1, r );
	t[num].Max = t[num].Hmax = max( t[lson].Max, t[rson].Max );
}

void pushup( int num ) {
	t[num].Max = max( t[lson].Max, t[rson].Max );
	t[num].Hmax = max( t[lson].Hmax, t[rson].Hmax );
}

void down( int num, int add, int Hadd ) {
	if( t[num].Htag != -inf )
		t[num].Htag = max( t[num].Htag, t[num].tag + Hadd ), t[num].tag += add;
	else
		t[num].Hadd = max( t[num].Hadd, t[num].add + Hadd ), t[num].add += add;
}

void pushdown( int num, int l, int r ) {
	if( t[num].tag == -inf and ! t[num].add ) return;
	t[num].Hmax = max( t[num].Hmax, max( t[num].Htag, t[num].Max + t[num].Hadd ) );
	if( t[num].add ) {
		t[num].Max += t[num].add;
		if( l ^ r ) {
			down( lson, t[num].add, t[num].Hadd );
			down( rson, t[num].add, t[num].Hadd ); 
		} 
	}
	if( t[num].tag != -inf ) {
		t[num].Max = t[num].tag;
		if( l ^ r ) {
			t[lson].tag = t[rson].tag = t[num].tag;
			t[lson].Htag = max( t[lson].Htag, t[num].Htag );
			t[rson].Htag = max( t[rson].Htag, t[num].Htag );
		}
	}
	t[num].add = t[num].Hadd = 0;
	t[num].tag = t[num].Htag = -inf;
}

void add( int num, int l, int r, int L, int R, int val ) {
	pushdown( num, l, r );
	if( R < l or r < L ) return;
	if( L <= l and r <= R ) {
		if( t[num].tag != -inf ) 
			t[num].tag += val, t[num].Htag = max( t[num].Htag, t[num].tag );
		else 
			t[num].add += val, t[num].Hadd = max( t[num].Hadd, t[num].add );
		pushdown( num, l, r );
		return;
	}
	pushdown( num, l, r );
	int mid = ( l + r ) >> 1;
	add( lson, l, mid, L, R, val );
	add( rson, mid + 1, r, L, R, val );
	pushup( num );
}

void modify( int num, int l, int r, int L, int R, int val ) {
	pushdown( num, l, r );
	if( R < l or r < L ) return;
	if( L <= l and r <= R ) {
		t[num].tag = val;
		t[num].Htag = max( t[num].Htag, val );
		pushdown( num, l, r );
		return;
	}
	pushdown( num, l, r );
	int mid = ( l + r ) >> 1;
	modify( lson, l, mid, L, R, val );
	modify( rson, mid + 1, r, L, R, val );
	pushup( num );
}

int query_max( int num, int l, int r, int L, int R ) {
	if( R < l or r < L ) return -inf;
	pushdown( num, l, r );
	if( L <= l and r <= R ) return t[num].Max;
	int mid = ( l + r ) >> 1;
	return max( query_max( lson, l, mid, L, R ), query_max( rson, mid + 1, r, L, R ) );
}

int queryHmax( int num, int l, int r, int L, int R ) {
	if( R < l or r < L ) return -inf;
	pushdown( num, l, r );
	if( L <= l and r <= R ) return t[num].Hmax;
	int mid = ( l + r ) >> 1;
	return max( queryHmax( lson, l, mid, L, R ), queryHmax( rson, mid + 1, r, L, R ) );
}

signed main() {
	int n, m, l, r, x; char opt[5];
	scanf( "%lld", &n );
	for( int i = 1;i <= n;i ++ ) scanf( "%lld", &a[i] );
	build( 1, 1, n );
	scanf( "%lld", &m );
	while( m -- ) {
		scanf( "%s %lld %lld", opt, &l, &r );
		switch ( opt[0] ) {
			case 'Q' : { printf( "%lld\n", query_max( 1, 1, n, l, r ) ); break; }
			case 'A' : { printf( "%lld\n", queryHmax( 1, 1, n, l, r ) ); break; }
			case 'P' : { scanf( "%lld", &x ); add( 1, 1, n, l, r, x );   break; }
			case 'C' : { scanf( "%lld", &x ); modify( 1, 1, n, l, r, x );break; }
		}
	}
	return 0;
}

【清华集训2015】V

UOJ164

整那么高大上的物理电阻屁用没有

操作

  • 区间加
  • 区间减
  • 区间赋值
  • 查询单点值
  • 查询单点历史最大值

这题很巧的转化将多个操作合并成了一种形式

将标记改写成(a,b)形式，标记对值的贡献转移形式改写成x←max(x+a,b)

  • 区间加：(val,-inf)
  • 区间减：(-val,-inf)
  • 区间赋值：(-inf,val)

标记的合并可以推出来，因为加法对取最大值满足分配率

  • 假设原来的标记为(a1,b1)，新来标记为(a2,b2)
  • max ? ( x + a 1 , b 1 ) ← ( a 2 , b 2 ) ? max ? ( max ? ( x + a 1 , b 1 ) + a 2 , b 2 ) ? max ? ( max ? ( x + a 1 + a 2 , b 1 + a 2 ) , b 2 ) \max(x+a_1,b_1)\leftarrow (a_2,b_2)\Rightarrow \max\Big(\max(x+a_1,b_1)+a_2,b_2\Big)\Rightarrow \max\Big(\max(x+a_1+a_2,b_1+a_2),b_2\Big) max(x+a1?,b1?)←(a2?,b2?)?max(max(x+a1?,b1?)+a2?,b2?)?max(max(x+a1?+a2?,b1?+a2?),b2?)
  • 新来标记合并最后即为 x ← max ? ( x + a 1 + a 2 , max ? ( a 2 + b 1 , b 2 ) ) x\leftarrow \max\Big(x+a_1+a_2,\max(a_2+b_1,b_2)\Big) x←max(x+a1?+a2?,max(a2?+b1?,b2?))

考虑当前最大值的更新

两个标记取 m a x \rm max max相当于两个分段一次函数取 m a x \rm max max

m a x ( ( a 1 , b 1 ) , ( a 2 , b 2 ) ) = ( m a x ( a 1 , a 2 ) , m a x ( b 1 , b 2 ) ) \rm max\Big((a_1,b_1),(a_2,b_2))=(max(a_1,a_2),max(b_1,b_2)\Big) max((a1?,b1?),(a2?,b2?))=(max(a1?,a2?),max(b1?,b2?))

在这里插入图片描述

再考虑历史最大值的更新

(a0,b0)表示当前，(a1,b1)表示历史最大值，(c0,d0)表示传递点当前，(c1,d1)表示传递点历史最大

合并(a0,b0)和(c0,d0)： ( a 0 + c 0 , max ? ( b 0 + c 0 , d 0 ) ) \Big(a_0+c_0,\max(b_0+c_0,d_0)\Big) (a0?+c0?,max(b0?+c0?,d0?))

合并(a1,b1)和(c1,d1)，先把(c1,d1)作用在(a0,b0)上， ( a 0 + c 1 , max ? ( b 0 + c 1 , d 1 ) ) \Big(a_0+c_1,\max(b_0+c_1,d_1)\Big) (a0?+c1?,max(b0?+c1?,d1?))

再和(a1,b1)取max： ( max ? ( a 1 , a 0 + c 1 ) , max ? ( b 1 , b 0 + c 1 , d 1 ) ) \Big(\max(a_1,a_0+c_1),\max(b_1,b_0+c_1,d_1)\Big) (max(a1?,a0?+c1?),max(b1?,b0?+c1?,d1?))

（a,b相当于儿子，c,d代表父亲的信息）

#include <cstdio>
#include <iostream>
using namespace std;
#define maxn 500005
#define int long long
#define lson num << 1
#define rson num << 1 | 1
struct node {
	int a, b, maxa, maxb;
}t[maxn << 2];
int w[maxn];
const int inf = 1e18;

void build( int num, int l, int r ) {
	t[num].a = t[num].maxa = 0;
	t[num].b = t[num].maxb = -inf;
	if( l == r ) return;
	int mid = l + r >> 1;
	build( lson, l, mid );
	build( rson, mid + 1, r );
}

void pushdown( int num ) {
	if( ! t[num].a and t[num].b == -inf ) return;
	t[lson].maxa = max( t[lson].maxa, t[lson].a + t[num].maxa );
	t[lson].maxb = max( t[lson].maxb, max( t[lson].b + t[num].maxa, t[num].maxb ) );
	t[rson].maxa = max( t[rson].maxa, t[rson].a + t[num].maxa );
	t[rson].maxb = max( t[rson].maxb, max( t[rson].b + t[num].maxa, t[num].maxb ) );
	t[lson].a = max( t[lson].a + t[num].a, -inf );
	t[lson].b = max( t[lson].b + t[num].a, t[num].b );
	t[rson].a = max( t[rson].a + t[num].a, -inf );
	t[rson].b = max( t[rson].b + t[num].a, t[num].b );
	t[num].a = t[num].maxa = 0;
	t[num].b = t[num].maxb = -inf;
}

void modify( int num, int l, int r, int L, int R, int a, int b ) {
	if( r < L or R < l ) return;
	if( L <= l and r <= R ) {
		t[num].a = max( t[num].a + a, -inf );
		t[num].b = max( t[num].b + a, b );
		t[num].maxa = max( t[num].a, t[num].maxa );
		t[num].maxb = max( t[num].b, t[num].maxb );
		return;
	}
	pushdown( num );
	int mid = l + r >> 1;
	modify( lson, l, mid, L, R, a, b );
	modify( rson, mid + 1, r, L, R, a, b );
}

int query( int num, int l, int r, int pos, int k ) {
	if( l == r ) {
		if( ! k ) return max( w[l] + t[num].a, t[num].b );
		else return max( w[l] + t[num].maxa, t[num].maxb );
	}
	pushdown( num );
	int mid = l + r >> 1;
	if( pos <= mid ) return query( lson, l, mid, pos, k );
	else return query( rson, mid + 1, r, pos, k );
}

signed main() {
	int n, m;
	scanf( "%lld %lld", &n, &m );
	for( int i = 1;i <= n;i ++ ) scanf( "%lld", &w[i] );
	build( 1, 1, n );
	for( int i = 1, opt, l, r, x;i <= m;i ++ ) {
		scanf( "%lld", &opt );
		switch ( opt ) {
			case 1 : { scanf( "%lld %lld %lld", &l, &r, &x ), modify( 1, 1, n, l, r, x, 0 ); break; }
			case 2 : { scanf( "%lld %lld %lld", &l, &r, &x ), modify( 1, 1, n, l, r, -x, 0 ); break; }
			case 3 : { scanf( "%lld %lld %lld", &l, &r, &x ), modify( 1, 1, n, l, r, -inf, x ); break; }
			case 4 : { scanf( "%lld", &x ), printf( "%lld\n", query( 1, 1, n, x, 0 ) ); break; }
			case 5 : { scanf( "%lld", &x ), printf( "%lld\n", query( 1, 1, n, x, 1 ) ); break; }
		}
	}
	return 0;
}

Naive Operations

HDU6315

刚开始区间全为 0 0 0，每次区间只 + 1 +1 +1

记录区间的最小值，

当最小值为 0 0 0的时候，说明多叠加了一个 b i b_i bi?的倍数

答案增加 1 1 1，然后重新把最小值置位 b i b_i bi? （这俩操作要走到叶子节点后再实行）

否则就打上整体 ? 1 -1 ?1的标记

#include <cstdio>
#include <iostream>
using namespace std;
#define maxn 100005
#define int long long
#define lson num << 1
#define rson num << 1 | 1
struct node {
	int sum, tag, Min;
}t[maxn << 2];
int b[maxn];

void build( int num, int l, int r ) {
	t[num].tag = t[num].sum = 0;
	if( l == r ) { t[num].Min = b[l]; return; }
	int mid = l + r >> 1;
	build( lson, l, mid );
	build( rson, mid + 1, r );
	t[num].Min = min( t[lson].Min, t[rson].Min );
}

void pushdown( int num ) {
	if( ! t[num].tag ) return;
	t[lson].tag += t[num].tag;
	t[rson].tag += t[num].tag;
	t[lson].Min -= t[num].tag;
	t[rson].Min -= t[num].tag;
	t[num].tag = 0;
}

void modify( int num, int l, int r, int L, int R ) {
	if( R < l or r < L ) return;
	if( L <= l and r <= R ) {
		t[num].Min --;
		if( t[num].Min ) { t[num].tag ++; return; }
		else if( l == r ) { t[num].sum ++, t[num].Min = b[l]; return; }
	}
	pushdown( num );
	int mid = l + r >> 1;
	modify( lson, l, mid, L, R );
	modify( rson, mid + 1, r, L, R );
	t[num].sum = t[lson].sum + t[rson].sum;
	t[num].Min = min( t[lson].Min, t[rson].Min );
}

int query( int num, int l, int r, int L, int R ) {
	if( r < L or R < l ) return 0;
	if( L <= l and r <= R ) return t[num].sum;
	pushdown( num );
	int mid = l + r >> 1;
	return query( lson, l, mid, L, R ) + query( rson, mid + 1, r, L, R );
}

signed main() {
	int n, Q, l, r; char opt[10];
	while( ~ scanf( "%lld %lld", &n, &Q ) ) {
		for( int i = 1;i <= n;i ++ ) scanf( "%lld", &b[i] );
		build( 1, 1, n );
		for( int i = 1;i <= Q;i ++ ) {
			scanf( "%s %d %d", opt, &l, &r );
			if( opt[0] == 'a' ) modify( 1, 1, n, l, r );
			else printf( "%lld\n", query( 1, 1, n, l, r ) );
		}
	}
	return 0;
}

Picture

HDU1828

扫描线求矩阵周长模板题

img

从下往上扫描线扫，横线长度：现在这次总区间被覆盖的长度和上一次总区间被覆盖的长度之差的绝对值

而竖线长度为，区间的段数*2，乘以 2 2 2是因为一段区间左右各一条

e.g. 段数 c n t cnt cnt的计算

  • 若区间[0,10]被[1,2][4,5]覆盖，则cnt=2
  • 若区间[0,10]被[1,3][4,5]覆盖，则cnt=1（两区间刚好连在一起）
  • 若区间[0,10]被[1,5][2,6]覆盖，则cnt=1（两区间连起来还是一段）

扫描线中的线段树的一个节点代表一个单位长度线段

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
#define maxn 200005
#define lson num << 1
#define rson num << 1 | 1
struct node {
	int l, r, h, op;
	node(){}
	node( int L, int R, int H, int Op ) {
		l = L, r = R, h = H, op = Op;
	}
}E[maxn];
struct tree {
	int l, r, len, cnt, tag, flag_l, flag_r;
}t[maxn << 2];

bool cmp( node x, node y ) { return x.h < y.h; }

void build( int num, int l, int r ) {
	t[num].l = l, t[num].r = r;
	t[num].len = t[num].cnt = t[num].tag = t[num].flag_l = t[num].flag_r = 0;
	if( l == r ) return;
	int mid = l + r >> 1;
	build( lson, l, mid );
	build( rson, mid + 1, r );
}

void pushup( int num ) {
	if( t[num].tag ) {
		t[num].len = t[num].r - t[num].l + 1;
		t[num].cnt = t[num].flag_l = t[num].flag_r = 1;
	}
	else if( t[num].l == t[num].r )
		t[num].len = t[num].cnt = t[num].flag_l = t[num].flag_r = 0;
	else {
		t[num].len = t[lson].len + t[rson].len;
		t[num].cnt = t[lson].cnt + t[rson].cnt - ( t[lson].flag_r and t[rson].flag_l );
		t[num].flag_l = t[lson].flag_l, t[num].flag_r = t[rson].flag_r;
	}
}

void modify( int num, int l, int r, int val ) {
	if( t[num].r < l or r < t[num].l ) return;
	if( l <= t[num].l and t[num].r <= r ) {
		t[num].tag += val;
		pushup( num );
		return;
	}
	modify( lson, l, r, val );
	modify( rson, l, r, val );
	pushup( num );
}

int Fabs( int x ) { return x < 0 ? -x : x; }

int main() {
	int n, x1, y1, x2, y2;
	while( ~ scanf( "%d", &n ) ) {
		int L = 1e9, R = -1e9;
		for( int i = 1;i <= n;i ++ ) {
			scanf( "%d %d %d %d", &x1, &y1, &x2, &y2 );
			E[i] = node( x1, x2, y1, 1 );
			E[i + n] = node( x1, x2, y2, -1 );
			L = min( L, x1 );
			R = max( R, x2 );
		}
		n <<= 1; R --;
		sort( E + 1, E + n + 1, cmp );
		build( 1, L, R );
		int ans = 0, lst = 0;
		for( int i = 1;i <= n;i ++ ) {
			modify( 1, E[i].l, E[i].r - 1, E[i].op );
			ans += Fabs( t[1].len - lst ) + 2 * t[1].cnt * ( E[i + 1].h - E[i].h );
			lst = t[1].len;
		}
		printf( "%d\n", ans );
	}
	return 0;
}

Walking Race

POJ3162

用两次栈模拟 d p dp dp求出以每个点为端点的最长路径

用线段树维护区间内的路径最大值/最小值

尺取法，双指针判断区间 [ l , r ] [l,r] [l,r]是否在 m m m限制内

#include <stack>
#include <cstdio>
#include <vector>
#include <iostream>
using namespace std;
#define maxn 1000005
#define lson num << 1
#define rson num << 1 | 1
const int inf = 1e9;
int n, m;
bool vis[maxn];
int maxlen[maxn];
stack < int > sta;
vector < pair < int, int > > G[maxn];

struct node { 
	int fa, d, Max, id, sub_max, sub_id;
	void clear( int f, int dis ) { fa = f, d = dis, Max = id = sub_max = sub_id = 0; }	
}MS[maxn];

void dfs1() {
	for( int i = 1;i <= n;i ++ ) vis[i] = 0;
	sta.push( 1 ), MS[1].clear( 0, 0 );
	while( ! sta.empty() ) {
		int u = sta.top();
		if( ! vis[u] )
			for( int i = 0;i < G[u].size();i ++ ) {
				int v = G[u][i].first, dis = G[u][i].second;
				if( v == MS[u].fa ) continue;
				else MS[v].clear( u, dis ), sta.push( v );
			}
		else {
			sta.pop();
			for( int i = 0;i < G[u].size();i ++ ) {
				int v = G[u][i].first, dis = G[u][i].second;
				int len = MS[v].Max + dis;
				if( len > MS[u].Max ) {
					MS[u].sub_max = MS[u].Max;
					MS[u].sub_id = MS[u].id;
					MS[u].Max = len;
					MS[u].id = v;
				}
				else if( len > MS[u].sub_max ) {
					MS[u].sub_max = len;
					MS[u].sub_id = v;
				}
			}
		}
		vis[u] = 1;
	}
}

void dfs2() {
	sta.push( 1 );
	while( ! sta.empty() ) {
		int u = sta.top(); sta.pop();
		for( int i = 0;i < G[u].size();i ++ ) {
				int v = G[u][i].first;
			if( v == MS[u].fa ) continue;
			else sta.push( v );
		}
		maxlen[u] = MS[u].Max;
		if( u == 1 ) continue;
		else {
			int fa = MS[u].fa, len;
			if( MS[fa].id == u ) len = MS[fa].sub_max + MS[u].d;
			else len = MS[fa].Max + MS[u].d;
			maxlen[u] = max( maxlen[u], len );
			if( len > MS[u].Max ) {
				MS[u].sub_max = MS[u].Max;
				MS[u].sub_id = MS[u].id;
				MS[u].Max = len;
				MS[u].id = fa;
			}
			else if( len > MS[u].sub_max ) {
				MS[u].sub_max = len;
				MS[u].sub_id = fa;
			}
		}
	}
}

struct tree { int Min, Max; }t[maxn << 2];

void build( int num, int l, int r ) {
	if( l == r ) { t[num].Min = t[num].Max = maxlen[l]; return; }
	int mid = l + r >> 1;
	build( lson, l, mid );
	build( rson, mid + 1, r );
	t[num].Max = max( t[lson].Max, t[rson].Max );
	t[num].Min = min( t[lson].Min, t[rson].Min );
}

int query_min( int num, int l, int r, int L, int R ) {
	if( r < L or R < l ) return inf;
	if( L <= l and r <= R ) return t[num].Min;
	int mid = l + r >> 1;
	return min( query_min( lson, l, mid, L, R ), query_min( rson, mid + 1, r, L, R ) );
}

int query_max( int num, int l, int r, int L, int R ) {
	if( r < L or R < l ) return -inf;
	if( L <= l and r <= R ) return t[num].Max;
	int mid = l + r >> 1;
	return max( query_max( lson, l, mid, L, R ), query_max( rson, mid + 1, r, L, R ) );
}

int main() {
	int l, r, minn, maxx;
	while( ~ scanf( "%d %d", &n, &m ) ) {
		for( int i = 1;i <= n;i ++ ) G[i].clear();
		for( int i = 2, fa, d;i <= n;i ++ ) {
			scanf( "%d %d", &fa, &d );
			G[fa].push_back( make_pair( i, d ) );
		}
		dfs1(), dfs2(), build( 1, 1, n );
		l = r = 1, minn = maxx = maxlen[1];
		int ans = 0;
		while( l <= r and r <= n ) {
			if( maxx - minn <= m ) {
				ans = max( ans, r - l + 1 );
				r ++;
				minn = min( minn, maxlen[r] );
				maxx = max( maxx, maxlen[r] );
			}
			else {
				l ++;
				minn = query_min( 1, 1, n, l, r );
				maxx = query_max( 1, 1, n, l, r );
			}
			if( ans > n - l ) break;
		}
		printf( "%d\n", ans );
	}
	return 0;
}
  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用：海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题＜有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2021-08-26 12:21:37  更:2021-08-26 12:23:42 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年12日历 -2024/12/29 7:57:21-

图片自动播放器
↓图片自动播放器↓ 		TxT小说阅读器
↓语音阅读,小说下载,古典文学↓ 		一键清除垃圾
↓轻轻一点,清除系统垃圾↓ 		图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码
数据统计