jq特效网站模板,网站建设 请示,投资1元赚1000,比较好的h5网站problem
洛谷链接
solution
定理 若 ijijij 且 i,ji,ji,j 联通#xff0c;则必有 k∈(i,j)k\in(i,j)k∈(i,j) 也与 i,ji,ji,j 联通。
下面给出证明#xff0c;挺显然的。
若 aiaja_ia_jaiaj#xff0c;则一定有 aiak∨akaja_i…problem
洛谷链接
solution
定理 若 ijijij 且 i,ji,ji,j 联通则必有 k∈(i,j)k\in(i,j)k∈(i,j) 也与 i,ji,ji,j 联通。
下面给出证明挺显然的。
若 aiaja_ia_jaiaj则一定有 aiak∨akaja_ia_k\vee a_ka_jaiak∨akaj 成立。若 aiaja_ia_jaiaj则一定有一个 xixixi 满足 axai∧axaja_xa_i\wedge a_xa_jaxai∧axaj 使得 i,ji,ji,j 间接联通。 若 akaxa_ka_xakax则有 k−jk-jk−j 联通。若 axaka_xa_kaxak则有 k−xk-xk−x 联通。
所以一个连通块一定对应的是数组 aaa 的一段连续区间。
也就是说所有连通块将数组划分成若干个互不相交且并集为整个数组的区间。
考虑相邻两个连通块假设前一个联通块的左右端点为 l1,r1l_1,r_1l1,r1则后一个联通块的左右端点为 r11(l2),r2r_11(l_2),r_2r11(l2),r2。
当且仅当 min{ai∣i∈[l1,r1]}max{ai∣i∈[l2,r2]}\min\{a_i|i\in [l_1,r_1]\}\max\{a_i|i\in[l_2,r_2]\}min{ai∣i∈[l1,r1]}max{ai∣i∈[l2,r2]} 两个联通块才不会合并。
进一步讲点 kkk 能够成为一个连通块的分断点当且仅当 min{ai∣i≤k}max{ai∣ki}\min\{a_i|i\le k\}\max\{a_i|ki\}min{ai∣i≤k}max{ai∣ki}。
不妨将 ai≥aka_i\ge a_kai≥ak 的位置设为 111aiaka_ia_kaiak 的设为 000将这个新数组表示为 f(k)f(k)f(k)与 kkk 有关。
则发现当 kkk 为分断点的时候f(k)f(k)f(k) 的长相一定是 111...11⏟k000...00\underbrace{111...11}_{k}000...00k111...11000...00。
换言之当 kkk 为分断点的时候f(k)f(k)f(k) 中 ai≠ai1a_i\neq a_{i1}aiai1 的 iii 有且仅有一个。
当然 f(k)f(k)f(k) 的长相有很多种。但如果 kkk 成为分断点那么 f(k)f(k)f(k) 就只能有一种长相。
换个角度讲令 wmax{ai∣ki}w\max\{a_i|ki\}wmax{ai∣ki}将 www 的位置设为 111≤w\le w≤w 的设为 000将新数组依旧表示为 f(w)f(w)f(w)。
则 f(w)f(w)f(w) 的长相一定也是 111...11⏟k000...00\underbrace{111...11}_{k}000...00k111...11000...00。
确定一个满足条件的 www 后的 kkk 也是唯一的。所以没必要枚举断点 kkk只需要枚举 www 即可。
也就是说只需要统计有多少个 www 对应的 f(w)f(w)f(w) 长相是这样的即有且仅有一对相邻的 101010。
为了规避全 000 和全 111也就是 wmin/max{ai∣i∈[1,n]}w\min/\max\{a_i|i\in[1,n]\}wmin/max{ai∣i∈[1,n]} 的情况这个时候是没有一对 101010 的。
不妨令 a0∞,an10a_0∞,a_{n1}0a0∞,an10。则满足条件的 www 的 f(w)f(w)f(w) 有且仅有一对相邻的 101010。
以权值 www 为下标建立线段树记录每个叶子对应 f(x)f(x)f(x) 长相中 101010 的对数。
最后统计多少个位置的对数为 111 即可。
考虑修改 aia_iai 会对 w∈[min{ai−1,ai},max{ai−1,ai})⋃[min{ai,ai1},max{ai,ai1})w\in\Big[\min\{a_{i-1},a_i\},\max\{a_{i-1},a_{i}\}\Big)\bigcup\Big[\min\{a_{i},a_{i1}\},\max\{a_{i},a_{i1}\}\Big)w∈[min{ai−1,ai},max{ai−1,ai})⋃[min{ai,ai1},max{ai,ai1}) 造成贡献变化。
例如 w∈[min{ai−1,ai},max{ai−1,ai})w\in\Big[\min\{a_{i-1},a_i\},\max\{a_{i-1},a_{i}\}\Big)w∈[min{ai−1,ai},max{ai−1,ai}) 时 ai−1,aia_{i-1},a_iai−1,ai 会构成一对 010101在线段树上将这个区间整体 111 即可。
注意到 ai−1,ai1a_{i-1},a_{i1}ai−1,ai1 可能越界不妨设 a0lim,an10a_0\lim,a_{n1}0a0lim,an10那么不管 iii 位置所有 www 至少都会有 111 对 010101。
线段树很难做到快速查询哪些位置是 111。但是现在所有的 www 的 010101 个数 ≥1\ge 1≥1。
就可以用线段树统计最小值和个数了。当且仅当最小值为 111 的时候再记录答案即可。
当然要注意只有当前出现在 aaa 数组里的 www即 waiwa_iwai才能在线段树中统计代表 www 的叶子节点是否贡献。
code
#include bits/stdc.h
using namespace std;
#define maxn 500005
#define lim 1000001
int n, q;
int a[maxn];
struct node { int sum, tag, cnt; }t[lim 5 2];#define lson now 1
#define rson now 1 | 1
#define mid (l r 1)void pushup( int now ) {if( t[lson].sum t[rson].sum ) t[now].sum t[lson].sum, t[now].cnt t[lson].cnt;else if( t[lson].sum t[rson].sum ) t[now].sum t[rson].sum, t[now].cnt t[rson].cnt;elset[now].sum t[lson].sum, t[now].cnt t[lson].cnt t[rson].cnt;
}void pushdown( int now ) {if( t[now].tag ) {t[lson].sum t[now].tag;t[rson].sum t[now].tag;t[lson].tag t[now].tag;t[rson].tag t[now].tag;t[now].tag 0;}
}void modify( int now, int l, int r, int L, int R, int x ) {if( R l or r L ) return;if( L l and r R ) {t[now].sum x;t[now].tag x;return;}pushdown( now );modify( lson, l, mid, L, R, x );modify( rson, mid 1, r, L, R, x );pushup( now );
}void modify( int now, int l, int r, int pos, int x ) {if( l r ) { t[now].cnt x; return; }pushdown( now );if( pos mid ) modify( lson, l, mid, pos, x );else modify( rson, mid 1, r, pos, x );pushup( now );
}int query( int now, int l, int r, int L, int R ) {if( R l or r L ) return 0;if( L l and r R ) return t[now].sum 1 ? t[now].cnt : 0;pushdown( now );return query( lson, l, mid, L, R ) query( rson, mid 1, r, L, R );
}void modify( int l, int r, int x ) {if( l r ) return;if( l r ) swap( l, r );modify( 1, 0, lim, l, r - 1, x );
}int main() {scanf( %d %d, n, q );for( int i 1;i n;i ) scanf( %d, a[i] );a[0] lim;for( int i 0;i n;i ) {modify( a[i], a[i 1], 1 );modify( 1, 0, lim, a[i], 1 );}while( q -- ) {int pos, x;scanf( %d %d, pos, x );modify( a[pos - 1], a[pos], -1 );modify( a[pos], a[pos 1], -1 );modify( 1, 0, lim, a[pos], -1 );a[pos] x;modify( a[pos - 1], a[pos], 1 );modify( a[pos], a[pos 1], 1 );modify( 1, 0, lim, a[pos], 1 );printf( %d\n, query( 1, 0, lim, 1, lim - 1 ) );}return 0;
}
