区域赛前在干什么?有没有空?可以来写线段树吗?
! https://zhuanlan.zhihu.com/p/665675388
AtCoder Beginner Contest 322 F
给你一个长度为 $N$ 的字符串 $S$ ,它由 0
和 1
组成。让 $S_i$ 表示 $S$ 的 $i$-th 字符。
按照给出的顺序处理 $Q$ 个查询。
每个查询由三个整数 $(c, L, R)$ 组成的元组表示,其中 $c$ 表示查询的类型。
- 当 $c=1$:对于每个整数 $i$,如果 $L \leq i \leq R$ 是 “1”,则将其改为 “0”;如果是 “0”,则将其改为 “1”。
- 当 $c=2$:假设$T$是提取$S$中$L_{th}到$R_{th}$字符后得到的字符串。打印$T$中连续
1
的最大个数。
考虑建立线段树。
维护每个区间的开头和结尾连续1的数量,连续0的数量。
维护最多的1的数量,最多的0的数量。反转的时候交换即可。
int n,q;
string s;
const int N = 5e5 + 100;
struct info {
int mss, mpre, msuf, sz, v;
int msso, mpreo, msufo;
info () {}
info(int a) : mss(a), mpre(a), msuf(a), v(a), sz(a | 1), msso(a ^ 1), mpreo(a ^ 1), msufo(a ^ 1) {}
};
struct tag {
int cnt;
};
struct node{
info val;
tag t;
}seg[N * 4];
tag operator + (const tag &t1, const tag &t2)
{
tag a;
a.cnt = t1.cnt + t2.cnt;
return a;
}
info operator + (const info &u, const tag &t)
{
info a;
a.mss = u.msso;
a.msso = u.mss;
a.mpre = u.mpreo;
a.mpreo = u.mpre;
a.msuf = u.msufo;
a.msufo = u.msuf;
a.v = u.sz - u.v;
a.sz = u.sz;
//a.vo = u.v;
return a;
}
info operator + (const info &l, const info &r)
{
info a;
a.mss = max({l.mss, r.mss, l.msuf + r.mpre});
a.msso = max({l.msso, r.msso, l.msufo + r.mpreo});
a.mpre = l.mpre + (l.v == l.sz ? r.mpre : 0);
a.mpreo = l.mpreo + (l.v == 0 ? r.mpreo : 0);
a.msuf = r.msuf + (r.v == r.sz ? l.msuf : 0);
a.msufo = r.msufo + (r.v == 0 ? l.msufo : 0);
a.sz = l.sz + r.sz;
a.v = l.v + r.v;
return a;
}
void update(int u){
seg[u].val = seg[u << 1].val + seg[u << 1 | 1].val;
}
void settag(int u,tag t)
{
seg[u].val = seg[u].val + t;
seg[u].t = seg[u].t + t;
}
void pushdown(int u)
{
if(seg[u].t.cnt % 2 == 1)
{
settag(u << 1, seg[u].t);
settag(u << 1 | 1, seg[u].t);
seg[u].t.cnt = 0;
}
else seg[u].t.cnt = 0;
}
void build(int u,int l,int r)
{
if(l == r) seg[u].val = info(s[l] - '0');
else{
int mid = (l + r) >> 1;
build(u << 1, l, mid);
build(u << 1 | 1,mid + 1, r);
update(u);
// 自下而上建树
}
}
void modify(int u,int l,int r,int ql,int qr, tag t)
{
if(l == ql && r == qr)
{
settag(u, t);
return;
}
int mid = (l + r) >> 1;
pushdown(u);
// [l , mid] [mid + 1, r]
if(qr <= mid) modify(u << 1, l, mid, ql, qr, t);
else if(ql >= mid + 1) modify(u << 1 | 1,mid + 1, r, ql, qr, t);
else{
// target [ql, mid] [mid + 1, qr]
modify(u << 1, l, mid, ql, mid, t);
modify(u << 1 | 1, mid + 1, r, mid + 1, qr, t);
}
update(u);
}
// [u ,l ,r]
// [ql ,qr] quite 参数 目标参数
// 核心 u ql qr
info query(int u,int l,int r,int ql,int qr)
{
if(l == ql && r == qr) return seg[u].val;
int mid = (l + r) >> 1;
// [l , mid] [mid + 1, r]
pushdown(u);
if(qr <= mid) return query(u << 1, l, mid, ql, qr);
else if(ql >= mid + 1) return query(u << 1 | 1,mid + 1, r, ql, qr);
else{
// target [ql, mid] [mid + 1, qr]
return query(u << 1, l, mid, ql, mid)
+ query(u << 1 | 1, mid + 1, r, mid + 1, qr);
}
}
void solve()
{
cin >> n >> q; cin >> s;
s = " " + s;
build(1,1,n);
for(int i = 0;i < q;i ++)
{
int ty,l,r;
cin >> ty >> l >> r;
//cout << ty << ' ' << l << ' ' << r << endl;
if(ty == 1) modify(1,1,n,l,r,tag{1});
else{
auto res = query(1,1,n,l,r);
//cout << res.mss << ' ' << res.mpre << ' ' << res.msuf << endl;
cout << res.mss << endl;
}
}
}
牛客练习赛 118 E Slove Equations 题目链接
化简后可以得到
$y - b = k * x$
$\begin{aligned} b &= b_{l} + b_{l + 1} \times \prod_{i=l}^{l}(a_{i}) + b_{l + 2} \times \prod_{i=l}^{l+1}(a_{i}) + … + b_{r} \times \prod_{i=l}^{r - 1}(a_{i}) \\ &= \sum_{i = l}^{r} { b_{i} \times \prod_{j=l}^{i - 1}(a_{j})} \end{aligned}$
$k = \prod_{i=l}^{r}(a_{i})$
const int mod = 998244353;
const int N = 3e5 + 1000;
int n;
pair<int,int> val[N];
pair<int,int> operator + (pair<int,int> l,pair<int,int> r)
{
pair<int,int> res;
res.first = l.first * r.first % mod;
res.second = (l.second + l.first * r.second % mod) % mod;
return res;
}
struct tree{
int l,r;
pair<int,int> sum;
} tr[N * 4];
void pushup(int u)
{
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void build(int u,int l,int r)
{
tr[u].l = l; tr[u].r = r;
if(l == r){
tr[u].sum = val[l];
return;
}
int mid = (l + r)>>1;
build(u << 1,l,mid);
build(u << 1 | 1,mid + 1, r);
pushup(u);
}
pair<int,int> query(int u,int l,int r)
{
if(l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
int mid = (tr[u].l + tr[u].r) >> 1;
// [l , mid] [mid + 1, r]
if(r <= mid) return query(u << 1,l,r);
else if(l >= mid + 1) return query(u << 1 | 1, l, r);
else{
// target [ql, mid] [mid + 1, qr]
return query(u << 1,l, mid)
+ query(u << 1 | 1, mid + 1, r);
}
}
int qmi(int a,int k,int p)
{
int res = 1;
for(;k;k>>=1,a=a*a%p) if(k&1) res=res*a%p;
return res;
}
void solve()
{
cin >> n;
for(int i = 1;i <= n;i ++) cin >> val[i].first;
for(int i = 1;i <= n;i ++) cin >> val[i].second;
build(1,1,n);
int q; cin >> q;
while(q --){
int l,r,y;
cin >> l >> r >> y;
pair<int,int> t = query(1,l,r);
if(t.first == 0){
if(t.second == y) cout << "inf" << endl;
else cout << "-1" << endl;
}
else
cout << ((y - t.second) * qmi(t.first,mod - 2,mod) % mod + mod) % mod << endl;
}
}