Educational Codeforces Round 137 (Rated for Div. 2) F. Intersection and Union（动态dp(线段树+矩阵+dp) /组合数学）

题目数轴上n(n3e5)条线段第i条线段[li,ri](0liri3e5)记第i条线段覆盖住的所有整点所在的集合为Si定义以下三种运算1. A∪B为A和B集合的并集2. A∩B为A和B集合的交集3. AB为A和B集合的对称差即A∪B-A∩B现有一个长度为n-1的未确定符号的数组op第i个符号可以是这三个符号中的一种求这种情况下式子的总和其中|S|表示S集合内元素的个数答案对998244353取模思路来源jiangly代码Young_sean代码自己乱搞的做法题解12026.10.1又随机到这个题发现自己当时写的ddp题解充满了强行理解又看不懂了找了一篇可读性更好的文章一下就又看懂了链接是https://www.luogu.com.cn/article/hwunqv7q以下是原博文对应代码1是比较想补的动态dp做法又称线段树维护矩阵优化dp代码来自jiangly感觉是个比较套路的做法考虑每个数的贡献则每个集合只有包含和不包含两种情况即这个值变成01操作也随之变成01之间的(与)、|(或)、^(异或)假设当前只有一条线段[l,r]其对应集合S1. 对于在[l,r]上的值x来说之前经历了若干次操作S1 op S2 op ...后若当前式子中的值为1则当其再op S时因为x在S上所以相当于op 1op 1时1有、|两种方式转移到1有^一种方式转移到01 op 1若当前式子中的值为0则当其再op S时op 1时0有|、^两种方式转移到1有一种方式转移到00 op 1即有矩阵M1M1.a[0][0] 1;M1.a[0][1] 2;M1.a[1][0] 1;M1.a[1][1] 2;2.同理若当前值x不在[l,r]上之前经历了若干次操作S1 op S2 op ...后若当前式子中的值为1则当其再op S时因为x不在S上所以相当于op 0op 0时1有|、^两种方式转移到1有一种方式转移到01 op 0若当前式子中的值为0则当其再op S时op 0时0没有方式能转移到1有|、、^三种方式转移到00 op 0即有矩阵M0M0.a[0][0] 3;M0.a[0][1] 0;M0.a[1][0] 1;M0.a[1][1] 2;而对于数x来说是否在S1对应的[l,r]相当于其初始状态的0/1值后续的S2-Sn相当于通过若干道转移关卡乘上若干个转移矩阵第i次根据x当前值以及x是否在Si上两个条件决定如何转移当增序从1遍历到3e5的时候对于一个区间[l,r]来说在[l,r]时只会乘矩阵M1不在[l,r]上时只会乘矩阵M0矩阵变化只会发生在进入l时以及离开r时遍历3e5个数后均摊下来变化是2*n次线段树维护矩阵即可注意初始的01值只能由x是否在[l1,r1]上决定不能钦定x0/1后走转移矩阵二者在答案上显然不同题解2组合数学统计每个数x的贡献仍然是考虑01序列首先对于每个点求覆盖其的最大区间的id即统计其出现的最后位置不妨以下以一个长度为5的01序列表示1. 10000即最后出现在首位置因为0 op 0不会得出1所以后续的操作都只能1 op 0即每次只能选、|两种操作种选法2. 01000即最后出现在第二位置后三个符号同理只能选、|而第一个符号只能选让结果为1的那两个0|110^11注意到11000同理第一个符号还是只能选让结果为1的那两个1|11111种选法3. 00100最后出现在[3,n]的位置x[x,n]之间这n-x个符号每个符号只能有、|两种选法x和x-1之间的符号也只能有两种选法视前面的值是0还是1决定选|还是|^[1,x-1]之间的符号有三种选法任选即可无论终值是什么都可以被x和x-1之间的符号捞回来对于位置x有种选法第二三两种情况可以统一对于每个值x统计贡献求和即可题解3自己的乱搞实则是手玩发现的规律后来找了找其合理性感觉其实和题解2本质相同因为存在1在出现了之后需要一直保持着到结尾结束的情况所以统计这个1是在什么时候最后一次出现的即如果枚举第i位是最后一次出现的1时强制给第i-1次操作后的值赋0心得其实后两种题解也涉及到一类经典问题若干个区间覆盖对于每个点求覆盖其的最大区间的id若干个区间覆盖求当前盖住的点的总个数去重本质是同一个问题允许离线有很多种写法1. 线段树维护区间或2. 线段树维护区间覆盖flag表示区间是否被完全覆盖已经被盖住后续就忽略均摊3. 从小到大遍历xl处加线段idr处删线段idset或优先队列维护当前最大的线段id代码1动态dp/线段树维护矩阵优化dp#include bits/stdc.h using i64 long long; constexpr int P 998244353; using i64 long long; // assume -P x 2P int norm(int x) { if (x 0) { x P; } if (x P) { x - P; } return x; } templateclass T T power(T a, i64 b) { T res 1; for (; b; b / 2, a * a) { if (b % 2) { res * a; } } return res; } struct Z { int x; Z(int x 0) : x(norm(x)) {} Z(i64 x) : x(norm(x % P)) {} int val() const { return x; } Z operator-() const { return Z(norm(P - x)); } Z inv() const { assert(x ! 0); return power(*this, P - 2); } Z operator*(const Z rhs) { x i64(x) * rhs.x % P; return *this; } Z operator(const Z rhs) { x norm(x rhs.x); return *this; } Z operator-(const Z rhs) { x norm(x - rhs.x); return *this; } Z operator/(const Z rhs) { return *this * rhs.inv(); } friend Z operator*(const Z lhs, const Z rhs) { Z res lhs; res * rhs; return res; } friend Z operator(const Z lhs, const Z rhs) { Z res lhs; res rhs; return res; } friend Z operator-(const Z lhs, const Z rhs) { Z res lhs; res - rhs; return res; } friend Z operator/(const Z lhs, const Z rhs) { Z res lhs; res / rhs; return res; } friend std::istream operator(std::istream is, Z a) { i64 v; is v; a Z(v); return is; } friend std::ostream operator(std::ostream os, const Z a) { return os a.val(); } };templateclass Info, class Merge std::plusInfo struct SegmentTree { const int n; const Merge merge; std::vectorInfo info; SegmentTree(int n) : n(n), merge(Merge()), info(4 std::__lg(n)) {} SegmentTree(std::vectorInfo init) : SegmentTree(init.size()) { std::functionvoid(int, int, int) build [](int p, int l, int r) { if (r - l 1) { info[p] init[l]; return; } int m (l r) / 2; build(2 * p, l, m); build(2 * p 1, m, r); pull(p); }; build(1, 0, n); } void pull(int p) { info[p] merge(info[2 * p], info[2 * p 1]); } void modify(int p, int l, int r, int x, const Info v) { if (r - l 1) { info[p] v; return; } int m (l r) / 2; if (x m) { modify(2 * p, l, m, x, v); } else { modify(2 * p 1, m, r, x, v); } pull(p); } void modify(int p, const Info v) { modify(1, 0, n, p, v); } Info rangeQuery(int p, int l, int r, int x, int y) { if (l y || r x) { return Info(); } if (l x r y) { return info[p]; } int m (l r) / 2; return merge(rangeQuery(2 * p, l, m, x, y), rangeQuery(2 * p 1, m, r, x, y)); } Info rangeQuery(int l, int r) { return rangeQuery(1, 0, n, l, r); } }; struct Matrix { Z a[2][2]; }; Matrix operator(const Matrix a, const Matrix b) { Matrix c; for (int i 0; i 2; i) { for (int j 0; j 2; j) { for (int k 0; k 2; k) { c.a[i][j] a.a[i][k] * b.a[k][j]; } } } return c; } Matrix M0, M1; int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); M0.a[0][0] 3; M0.a[0][1] 0; M0.a[1][0] 1; M0.a[1][1] 2; M1.a[0][0] 1; M1.a[0][1] 2; M1.a[1][0] 1; M1.a[1][1] 2; int n; std::cin n; std::vectorint l(n), r(n); int max 0; for (int i 0; i n; i) { std::cin l[i] r[i]; max std::max(max, r[i]); } max; std::vectorstd::vectorint add(max), del(max); for (int i 0; i n; i) { add[l[i]].push_back(i); del[r[i]].push_back(i); } int a0 0; SegmentTreeMatrix seg(std::vector(n - 1, M0)); Z ans 0; for (int i 0; i max; i) { for (auto j : add[i]) { if (j) { seg.modify(j - 1, M1); } else { a0 1; } } ans seg.info[1].a[a0][1]; for (auto j : del[i]) { if (j) { seg.modify(j - 1, M0); } else { a0 0; } } } std::cout ans \n; return 0; }代码2组合数学import random import sys import os import math from collections import Counter, defaultdict, deque from functools import lru_cache, reduce from itertools import accumulate, combinations, permutations from heapq import nsmallest, nlargest, heapify, heappop, heappush from io import BytesIO, IOBase from copy import deepcopy import threading import bisect BUFSIZE 4096 class FastIO(IOBase): newlines 0 def __init__(self, file): self._fd file.fileno() self.buffer BytesIO() self.writable x in file.mode or r not in file.mode self.write self.buffer.write if self.writable else None def read(self): while True: b os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE)) if not b: break ptr self.buffer.tell() self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr) self.newlines 0 return self.buffer.read() def readline(self): while self.newlines 0: b os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE)) self.newlines b.count(b\n) (not b) ptr self.buffer.tell() self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr) self.newlines - 1 return self.buffer.readline() def flush(self): if self.writable: os.write(self._fd, self.buffer.getvalue()) self.buffer.truncate(0), self.buffer.seek(0) class IOWrapper(IOBase): def __init__(self, file): self.buffer FastIO(file) self.flush self.buffer.flush self.writable self.buffer.writable self.write lambda s: self.buffer.write(s.encode(ascii)) self.read lambda: self.buffer.read().decode(ascii) self.readline lambda: self.buffer.readline().decode(ascii) sys.stdin, sys.stdout IOWrapper(sys.stdin), IOWrapper(sys.stdout) input lambda: sys.stdin.readline().rstrip(\r\n) class SortedList: def __init__(self, iterable[], _load200): Initialize sorted list instance. values sorted(iterable) self._len _len len(values) self._load _load self._lists _lists [values[i:i _load] for i in range(0, _len, _load)] self._list_lens [len(_list) for _list in _lists] self._mins [_list[0] for _list in _lists] self._fen_tree [] self._rebuild True def _fen_build(self): Build a fenwick tree instance. self._fen_tree[:] self._list_lens _fen_tree self._fen_tree for i in range(len(_fen_tree)): if i | i 1 len(_fen_tree): _fen_tree[i | i 1] _fen_tree[i] self._rebuild False def _fen_update(self, index, value): Update fen_tree[index] value. if not self._rebuild: _fen_tree self._fen_tree while index len(_fen_tree): _fen_tree[index] value index | index 1 def _fen_query(self, end): Return sum(_fen_tree[:end]). if self._rebuild: self._fen_build() _fen_tree self._fen_tree x 0 while end: x _fen_tree[end - 1] end end - 1 return x def _fen_findkth(self, k): Return a pair of (the largest idx such that sum(_fen_tree[:idx]) k, k - sum(_fen_tree[:idx])). _list_lens self._list_lens if k _list_lens[0]: return 0, k if k self._len - _list_lens[-1]: return len(_list_lens) - 1, k _list_lens[-1] - self._len if self._rebuild: self._fen_build() _fen_tree self._fen_tree idx -1 for d in reversed(range(len(_fen_tree).bit_length())): right_idx idx (1 d) if right_idx len(_fen_tree) and k _fen_tree[right_idx]: idx right_idx k - _fen_tree[idx] return idx 1, k def _delete(self, pos, idx): Delete value at the given (pos, idx). _lists self._lists _mins self._mins _list_lens self._list_lens self._len - 1 self._fen_update(pos, -1) del _lists[pos][idx] _list_lens[pos] - 1 if _list_lens[pos]: _mins[pos] _lists[pos][0] else: del _lists[pos] del _list_lens[pos] del _mins[pos] self._rebuild True def _loc_left(self, value): Return an index pair that corresponds to the first position of value in the sorted list. if not self._len: return 0, 0 _lists self._lists _mins self._mins lo, pos -1, len(_lists) - 1 while lo 1 pos: mi (lo pos) 1 if value _mins[mi]: pos mi else: lo mi if pos and value _lists[pos - 1][-1]: pos - 1 _list _lists[pos] lo, idx -1, len(_list) while lo 1 idx: mi (lo idx) 1 if value _list[mi]: idx mi else: lo mi return pos, idx def _loc_right(self, value): Return an index pair that corresponds to the last position of value in the sorted list. if not self._len: return 0, 0 _lists self._lists _mins self._mins pos, hi 0, len(_lists) while pos 1 hi: mi (pos hi) 1 if value _mins[mi]: hi mi else: pos mi _list _lists[pos] lo, idx -1, len(_list) while lo 1 idx: mi (lo idx) 1 if value _list[mi]: idx mi else: lo mi return pos, idx def add(self, value): Add value to sorted list. _load self._load _lists self._lists _mins self._mins _list_lens self._list_lens self._len 1 if _lists: pos, idx self._loc_right(value) self._fen_update(pos, 1) _list _lists[pos] _list.insert(idx, value) _list_lens[pos] 1 _mins[pos] _list[0] if _load _load len(_list): _lists.insert(pos 1, _list[_load:]) _list_lens.insert(pos 1, len(_list) - _load) _mins.insert(pos 1, _list[_load]) _list_lens[pos] _load del _list[_load:] self._rebuild True else: _lists.append([value]) _mins.append(value) _list_lens.append(1) self._rebuild True def discard(self, value): Remove value from sorted list if it is a member. _lists self._lists if _lists: pos, idx self._loc_right(value) if idx and _lists[pos][idx - 1] value: self._delete(pos, idx - 1) def remove(self, value): Remove value from sorted list; value must be a member. _len self._len self.discard(value) if _len self._len: raise ValueError({0!r} not in list.format(value)) def pop(self, index-1): Remove and return value at index in sorted list. pos, idx self._fen_findkth(self._len index if index 0 else index) value self._lists[pos][idx] self._delete(pos, idx) return value def bisect_left(self, value): Return the first index to insert value in the sorted list. pos, idx self._loc_left(value) return self._fen_query(pos) idx def bisect_right(self, value): Return the last index to insert value in the sorted list. pos, idx self._loc_right(value) return self._fen_query(pos) idx def count(self, value): Return number of occurrences of value in the sorted list. return self.bisect_right(value) - self.bisect_left(value) def __len__(self): Return the size of the sorted list. return self._len def __getitem__(self, index): Lookup value at index in sorted list. pos, idx self._fen_findkth(self._len index if index 0 else index) return self._lists[pos][idx] def __delitem__(self, index): Remove value at index from sorted list. pos, idx self._fen_findkth(self._len index if index 0 else index) self._delete(pos, idx) def __contains__(self, value): Return true if value is an element of the sorted list. _lists self._lists if _lists: pos, idx self._loc_left(value) return idx len(_lists[pos]) and _lists[pos][idx] value return False def __iter__(self): Return an iterator over the sorted list. return (value for _list in self._lists for value in _list) def __reversed__(self): Return a reverse iterator over the sorted list. return (value for _list in reversed(self._lists) for value in reversed(_list)) def __repr__(self): Return string representation of sorted list. return SortedList({0}).format(list(self)) def I(): return input() def II(): return int(input()) def MI(): return map(int, input().split()) def LI(): return list(input().split()) def LII(): return list(map(int, input().split())) def GMI(): return map(lambda x: int(x) - 1, input().split()) def LGMI(): return list(map(lambda x: int(x) - 1, input().split())) n II() intervals [] INT 998244353 for _ in range(n): intervals.append(LII()) nums [n] * (300001) tmp SortedList(list(range(300001))) for idx, (x, y) in enumerate(intervals[::-1]): pos tmp.bisect_left(x) while pos len(tmp) and tmp[pos] y: nums[tmp[pos]] idx tmp.remove(tmp[pos]) ans 0 for val in nums: if val n: continue if val n-2: res pow(2, n-1, INT) else: res pow(2, val 1, INT) * pow(3, n - 1 - val - 1, INT) ans (ans res) % INT print(ans)代码3自己的乱搞#includebits/stdc.h using namespace std; typedef long long ll; typedef unsigned long long ull; const int N3e510,mod998244353; int n,l[N],r[N],ans; struct node{ int cs,cov; node(){ cs0;cov-1; } }tr[N*4]; void up(int p){ tr[p].cstr[p1].cstr[p1|1].cs; } void bld(int p,int l,int r){ tr[p].cstr[p].cov0; if(lr){ return; } int mid(lr)1; bld(p1,l,mid); bld(p1|1,mid1,r); up(p); } void psd(int p,int l,int r){ if(tr[p].cov){ int mid(lr)/2; tr[p1].csmid-l1; tr[p1|1].csr-mid; tr[p1].covtr[p].cov; tr[p1|1].covtr[p].cov; tr[p].cov0; } } void upd(int p,int l,int r,int ql,int qr){ if(qllrqr){ tr[p].csr-l1; tr[p].cov1; return; } psd(p,l,r); int mid(lr)1; if(qlmid)upd(p1,l,mid,ql,qr); if(qrmid)upd(p1|1,mid1,r,ql,qr); up(p); } int ask(int p,int l,int r,int ql,int qr) { if(qllrqr)return tr[p].cs; psd(p,l,r); int res0,mid(lr)1; if(qlmid)resask(p1,l,mid,ql,qr); if(qrmid)resask(p1|1,mid1,r,ql,qr); return res; } int modpow(int x,int n,int mod){ int res1; for(;n;n1,x1ll*x*x%mod){ if(n1)res1ll*res*x%mod; } return res; } int main(){ scanf(%d,n); int invmodpow(3,mod-2,mod),three1; for(int i1;in;i){ scanf(%d%d,l[i],r[i]); if(in-2)three3ll*three%mod; } bld(1,0,3e5); for(int in;i1;--i){ upd(1,0,3e5,l[i],r[i]); if(i2)continue; //ans(ans1ll*three[max(0,i-3)]*two[n-i1]%mod*ask(1,1,n,1,n)%mod)%mod;// /3*2 if(i1)three1ll*three*inv%mod; three2ll*three%mod; //printf(ask:%d\n,ask(1,0,3e5,0,3e5)); ans(ans1ll*three*ask(1,0,3e5,0,3e5)%mod)%mod; } printf(%d\n,ans); return 0; }