Educational Codeforces Round 137 (Rated for Div. 2)

（线段树 + 思维）or 动态dp

[Problem - F - Codeforces](https://codeforces.com/contest/1743/problem/E)

题意

数轴上有 \(n\) 个线段 \([l,r]\;(0<=l<=r<=3*10^5)\) ，表示有一个集合 \(s_i\) 为 \([l,r]\)

有三种集合运算，交、并、异或（两个集合异或 = 并 - 交）

\(S=s_i\;op\;s_2\;op\;...\;op\;s_n\) ，对于 \(n-1\) 个 op 的选择，有 \(3^{n-1}\) 种，求这 \(3^{n-1}\) 个 S 的大小之和

思路1

单独考虑一个元素 \(x\), 设 \(a\) 为包含 x 的一个集合，\(b\) 为不包含 \(x\) 的一个集合
关键是发现如下性质：
1. 两个 b 搞不出来 x
2. a 交，并 a 可以保留 x，有 2 种
3. a 并，异或 b 可以保留 x，有 2 种
因此若最终想保留 x，则需要找到最后一个包含 x 的集合的下标 last （用线段树来维护单点最大值和区间赋值）

前 last - 2 个操作无所谓；后面的 n - last + 1 个操作只有 2 种选择才能保留 x

因此保留 x 的方案数为 \(3^{last-2}*2^{n-last+1}\) 个

思路2

同样单独考虑一个元素 x
设 \(f[i][0/1]\) 表示前 i 个集合操作完后，x 是否在当前集合中的方案数
当 x 在 \(s_i\) 中时
1. \(f[i][0]=f[i-1][0]+f[i-1][1]\)
2. \(f[i][1]=2*f[i-1][0]+2*f[i-1][1]\)
当 x 不在 \(s_i\) 中时
1. \(f[i][0]=3*f[i-1][0]+f[i-1][1]\)
2. \(f[i][1]=2*f[i-1][1]\)
但这样转移的复杂度为 \(O(n*3e5)\)
由于每个集合都是一个区间，可以用线段树来优化，可以对每个区间中所有数整体来转移
上述转移可写成矩阵的形式：
1. x 在 \(s_i\) 中时
\[\begin{bmatrix}
f[i][0]\\
f[i][1]
\end{bmatrix}=
\begin{bmatrix}
1&1\\
2&2
\end{bmatrix}*
\begin{bmatrix}
f[i-1][0]\\
f[i-1][1]
\end{bmatrix}
\]
1. x 不在 \(s_i\) 中时
  \[\begin{bmatrix}
  f[i][0]\\
  f[i][1]
  \end{bmatrix}=
  \begin{bmatrix}
  3&1\\
  2&0
  \end{bmatrix}*
  \begin{bmatrix}
  f[i-1][0]\\
  f[i-1][1]
  \end{bmatrix}
  \]
可用线段树对一个区间整体乘上一个矩阵

代码1

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"

typedef long long ll;

typedef pair<int, int> PII;

const int N = 3e5 + 10;

const int mod = 998244353;

int n;

struct SegmentTree {

   #define ls u << 1

   #define rs u << 1 | 1

   struct T {

       int l, r;

       ll v;

       ll add;

   }tr[N << 2];

   void pushup(int u) {

       tr[u].v = max(tr[ls].v, tr[rs].v);

   }

   void update(T& rt, int add)  {

       rt.add = add, rt.v = add;

   }

   void pushdown(int u) {

       if (tr[u].add) {

           update(tr[ls], tr[u].add);

           update(tr[rs], tr[u].add);

           tr[u].add = 0;

       }

   }

   void build(int u, int l, int r) {

       tr[u].l = l, tr[u].r = r, tr[u].v = tr[u].add = 0;

       if (tr[u].l == tr[u].r) {

           return ;

       }

       int mid = (tr[u].l + tr[u].r) >> 1;

       build(ls, l, mid), build(rs, mid + 1, r);

       pushup(u);

       return ;

   }

   void modify(int u, int l, int r, int v) {

       if (tr[u].l >= l && tr[u].r <= r) {

           update(tr[u], v);

           return ;

       }

       pushdown(u);

       int mid = (tr[u].l + tr[u].r) >> 1;

       if (l <= mid) modify(ls, l, r, v);

       if (r > mid) modify(rs, l, r, v);

       pushup(u);

       return ;

   }

   int query(int u, int l, int r) {

       if (tr[u].l >= l && tr[u].r <= r) {

           return tr[u].v;

       }

       pushdown(u);

       int mid = (tr[u].l + tr[u].r) >> 1;

       int res = 0;

       if (l <= mid) res = query(ls, l, r);

       if (r > mid) res = max(res, query(rs, l, r));

       return res;

   }

}tr;

ll qmi(ll a, ll b)

{

	ll ans = 1;

	while(b)

	{

		if (b & 1)

			ans = ans * a % mod;

		b >>= 1;

		a = a * a % mod;

	}

	return ans;

}

int main()

{

	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n;

	tr.build(1, 0, N - 10);

	for (int i = 1; i <= n; i++)

	{

		int l, r;

		cin >> l >> r;

		tr.modify(1, l, r, i);

	}

	ll ans = 0;

	for (int i = 0; i <= N - 10; i++)

	{

		int last = tr.query(1, i, i);

        if (last == 0)

            continue;

		int a = max(0, last - 2);

		int b = n - 1 - a;

		ans += qmi(3, a) * qmi(2, b) % mod;

		ans %= mod;

	}

	cout << ans << endl;

    return 0;

}

巴特西

Educational Codeforces Round 137 (Rated for Div. 2) - F. Intersection and Union

（线段树 + 思维）or 动态dp

题意

思路1

思路2

代码1

最新文章

热门文章