营销型网站建设的利与弊,wordpress域名修改,济南卓远网站建设公司,湖南信息网官方网站problem
给定数组 l,rl,rl,r。求有多少个非空集合 SSS#xff0c;满足 ∀i,j∈Sli≤j≤ri\forall_{i,j\in S}\ l_i\le j\le r_i∀i,j∈S li≤j≤ri。
集合内对于任意一个点而言#xff0c;其余点均能被自己的范围覆盖到。 n≤2e5n\le 2e5n≤2e5。
solution 分享一下…problem
给定数组 l,rl,rl,r。求有多少个非空集合 SSS满足 ∀i,j∈Sli≤j≤ri\forall_{i,j\in S}\ l_i\le j\le r_i∀i,j∈S li≤j≤ri。
集合内对于任意一个点而言其余点均能被自己的范围覆盖到。
n≤2e5n\le 2e5n≤2e5。
solution 分享一下考场心路历程考试是分了五个部分分的。 第一个部分分直接 2n2^n2n 暴枚很快拿下。 第二个部分分 n≤2000n\le 2000n≤2000一看就是 n2n^2n2 算法我就想到了固定集合选取点的最左最右点然后看有多少个点满足 li≤L∧R≤ri∧L≤i≤Rl_i\le L\wedge R\le r_i\wedge L\le i\le Rli≤L∧R≤ri∧L≤i≤R天哪太多的偏序关系了我直接抡 KD-tree\text{KD-tree}KD-tree好家伙大样例虽然对了却要跑 6s6s6s试问谁遭得住 第三个部分分 ri−li≤10r_i-l_i\le 10ri−li≤10。我就只枚举最左点然后暴搜/Hash\text{Hash}Hash 集合个数不超过 2102^{10}210算出来大约 2e82e82e8 但肯定跑不满。一看样例全过。测评最后结果 wa\text{wa}wa 了但这不重要了 第四个部分分5e45e45e4 可能是分块吧。对我没有太多帮助。 第五个部分分就是最大的范围了。 由第二个部分的枚举 l,rl,rl,r 我突然想到了前不久狂做 LCT\text{LCT}LCT 的一类连通性题。全都是枚举了右端点然后用线段树上的节点做左端点并用线段树维护答案个数。 这里我想类比做法蒋所有 [li,ri][l_i,r_i][li,ri] 全挂到 rir_iri 点下。 枚举 iii 做右端点然后线段树上的节点做左端点。 新右端点会对 [li,i][l_i,i][li,i] 都提供 111 的个数答案是 2cnt2^\text{cnt}2cnt每个数选或不选 当 iii 右移一位的时候就要去掉所有 rjir_jirji 的 jjj 曾经的贡献。 然后然后我发现强制左右端点后虽然不会算重但是应该算的是 2cnt−22^{cnt-2}2cnt−2去掉左右端点选和不选的考虑 结果这样又会影响我线段树的标记下放那我的线段树不是废了 最后不管是在线段树上维护个数还是直接维护贡献都无法正确避免 −2-2−2 带来的影响在主函数内我也无法去掉。我就直接开始摆烂了。。。 结果下午过来给小同志讲了一遍后没讲懂被她质疑的我就仔细想了一下突然想到了貌似大概也许可以这么来重构一遍直接过心中草泥马奔腾。。。 从左到右枚举集合的右端点 rrr最大的点。
然后线段树上的节点 lll 强制是集合的左端点且维护的信息是 l,rl,rl,r 做左右端点时的答案。
考虑统计右端点为 iii 的答案。
首先要激活线段树上的 iii 节点初始化为 111代表 [i,i][i,i][i,i] 集合。
然后统计线段树上 [li,i][l_i,i][li,i] 区间的答案。
接下来 iii 要右移 111我们需要重新修改维护线段树上的信息。 对区间 [li,i−1][l_i,i-1][li,i−1] 进行区间 ×2\times 2×2。 表示当这些区间中的节点为集合左端点时iii 是合法互达备选点存在选和不选的方案考虑。 但不能对 iii 也进行 ×2\times 2×2理由在心路历程后面提到它是被强制了的。 对所有 rjir_jirji 的 jjj从 i1i1i1 开始当右端点后jjj 就不可能再到达集合的右端点了再也不能成为合法互达备选点所以要把 jjj 之前提供的贡献全都去掉。 要进行 [lj,j−1][l_j,j-1][lj,j−1] 区间 /2/2/2以及节点 jjj 的直接赋 000。这样 jjj 就在也不可能成为集合左端点被纳入贡献了
时间复杂度 O(nlogn)O(n\log n)O(nlogn)。
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;
}
