problem

給定數組 $l,r$。求有多少個非空集合 $S$，滿足 ${?}_{i,j\in S}{l}_i\le j\le r_i$。

集合內對于任意一個點而言，其余點均能被自己的范圍覆蓋到。

$n\le 2e5$。

solution

分享一下考場心路歷程：考試是分了五個部分分的。

第一個部分分直接 $2^n$ 暴枚，很快拿下。

第二個部分分 $n\le 2000$，一看就是 $n^2$ 算法，我就想到了固定集合選取點的最左最右點，然后看有多少個點滿足 $l_i\le L\wedge R\le r_i\wedge L\le i\le R$，天哪太多的偏序關系了，我直接掄 $\text{KD-tree}$，好家伙大樣例雖然對了卻要跑 $6s$，試問誰遭得住？

第三個部分分 $r_i?l_i\le 10$。我就只枚舉最左點，然后暴搜/$\text{Hash}$ 集合個數，不超過 $2^{10}$，算出來大約 $2e8$ 但肯定跑不滿。一看樣例全過。（測評最后結果 $\text{wa}$ 了，但這不重要了）

第四個部分分，$5e4$ 可能是分塊吧。對我沒有太多幫助。

第五個部分分，就是最大的范圍了。

由第二個部分的枚舉 $l,r$ 我突然想到了前不久狂做 $\text{LCT}$ 的一類連通性題。全都是枚舉了右端點然后用線段樹上的節點做左端點，并用線段樹維護答案個數。

這里我想類比做法：蔣所有 $[l_i,r_i]$ 全掛到 $r_i$ 點下。

枚舉 $i$ 做右端點，然后線段樹上的節點做左端點。

新右端點會對 $[l_i,i]$ 都提供 $1$ 的個數（答案是 $2^{\text{cnt}}$，每個數選或不選）

當 $i$ 右移一位的時候，就要去掉所有 $r_j=i$ 的 $j$ 曾經的貢獻。

然后，然后，我發現強制左右端點后雖然不會算重，但是應該算的是 $2^{cnt?2}$（去掉左右端點選和不選的考慮）

結果這樣又會影響我線段樹的標記下放，那我的線段樹不是廢了？！！

最后不管是在線段樹上維護個數還是直接維護貢獻都無法正確避免 $?2$ 帶來的影響，在主函數內我也無法去掉。我就直接開始擺爛了。。。

結果下午過來，給小同志講了一遍后沒講懂，被她質疑的我就仔細想了一下，突然想到了貌似大概也許可以這么來，重構一遍直接過！心中草泥馬奔騰。。。

從左到右枚舉集合的右端點 $r$（最大的點）。

然后線段樹上的節點 $l$ 強制是集合的左端點，且維護的信息是 $l,r$ 做左右端點時的答案。

考慮統計右端點為 $i$ 的答案。

首先要激活線段樹上的 $i$ 節點，初始化為 $1$，代表 $[i,i]$ 集合。

然后統計線段樹上 $[l_i,i]$ 區間的答案。

接下來 $i$ 要右移 $+1$，我們需要重新修改維護線段樹上的信息。

• 對區間 $[l_i,i?1]$ 進行區間 $\times 2$。

  表示當這些區間中的節點為集合左端點時，$i$ 是合法互達備選點，存在選和不選的方案考慮。

  但不能對 $i$ 也進行 $\times 2$，理由在心路歷程后面提到，它是被強制了的。

• 對所有 $r_j=i$ 的 $j$，從 $i+1$ 開始當右端點后，$j$ 就不可能再到達集合的右端點了，再也不能成為合法互達備選點，所以要把 $j$ 之前提供的貢獻全都去掉。

  要進行 $[l_j,j?1]$ 區間 $/2$，以及節點 $j$ 的直接賦 $0$。（這樣 $j$ 就在也不可能成為集合左端點被納入貢獻了）

時間復雜度 $O(n\log n)$。

code

#include <bits/stdc++.h> using namespace std; #define maxn 200005 #define int long long #define mod 998244353namespace SGT {struct node { int cnt, tag; }t[maxn << 2];#define lson now << 1#define rson now << 1 | 1#define mid (l + r >> 1)void build( int now, int l, int r ) {t[now].tag = 1;if( l == r ) return;build( lson, l, mid );build( rson, mid + 1, r );}void pushdown( int now ) {if( t[now].tag == 1 ) return;( t[lson].tag *= t[now].tag ) %= mod;( t[rson].tag *= t[now].tag ) %= mod;( t[lson].cnt *= t[now].tag ) %= mod;( t[rson].cnt *= t[now].tag ) %= mod;t[now].tag = 1;}void modify( int now, int l, int r, int p, int x ) {if( l == r ) { t[now].cnt = x ? 1 : 0; return; }pushdown( now );if( p <= mid ) modify( lson, l, mid, p, x );else modify( rson, mid + 1, r, p, x );t[now].cnt = ( t[lson].cnt + t[rson].cnt ) % mod;}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].cnt *= x ) %= mod;( t[now].tag *= x ) %= mod;return;}pushdown( now );modify( lson, l, mid, L, R, x );modify( rson, mid + 1, r, L, R, x );t[now].cnt = ( t[lson].cnt + t[rson].cnt ) % mod;}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].cnt;pushdown( now );return query( lson, l, mid, L, R ) + query( rson, mid + 1, r, L, R );} }int n; int l[maxn], r[maxn]; vector < int > G[maxn]; signed main() {scanf( "%lld", &n );for( int i = 1;i <= n;i ++ ) scanf( "%lld", &l[i] );for( int i = 1;i <= n;i ++ ) scanf( "%lld", &r[i] );for( int i = 1;i <= n;i ++ ) G[r[i]].push_back( i );SGT :: build( 1, 1, n ); //線段樹上強制節點為選取集合最小值int ans = 0;int inv = mod + 1 >> 1;for( int i = 1;i <= n;i ++ ) { //強制選取的集合最大值SGT :: modify( 1, 1, n, i, 1 ); //把i激活 初始化1( ans += SGT :: query( 1, 1, n, l[i], i ) ) %= mod;SGT :: modify( 1, 1, n, l[i], i - 1, 2 ); //對于最小值屬于[l[i],i-1]的點 會有一個新的i可以互達for( int j : G[i] ) {SGT :: modify( 1, 1, n, l[j], j - 1, inv );SGT :: modify( 1, 1, n, j, 0 );}}printf( "%lld\n", ans );return 0; }

總結

以上是生活随笔為你收集整理的互达的集合（线段树）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。