P5445记录中提到的内容是什么？
摘要：收获比较大，就从做题记录与反思中单独拿出来了 首先注意到修改 ([i , i + 1]) 只影响了 query([l , i] , [i + 1 , r]) ，其中 (l) 是与 (i) 相连
收获比较大，就从做题记录与反思中单独拿出来了
首先注意到修改 \([i , i + 1]\) 只影响了 query([l , i] , [i + 1 , r]) ，其中 \(l\) 是与 \(i\) 相连通的最左的节点，\(r\) 是与 \(i + 1\) 相连通的最右的节点
询问是求有多少个时刻联通。可以把时间看作权值，\(i\) 时刻联通就将询问 \(+(q - i)\)，\(i\) 时刻断开就 \(-(q - i)\)
问题变为了矩阵加，单点求和。差分一下，变为单点加，前缀矩阵求和。
用动态开点线段树套树状数组。即可解决
总共要写三棵树，一棵用来维护是与 \(i\) 相连通的最左最右的节点，另外两颗是树套树
疑问：这个问题已经很久没有解决了。不会算线段树的空间复杂度。从 \(maxn \times 20\) 开到 \(\times 40\)，\(\times 60\) 最后到 \(\times 80\)，终于过了。提交记录
与教练讨论并查看 luogu 讨论区，得出结论：最坏情况下要开 \(4 q log^2 n\)。这是绝对MLE的。至于为什么能过，只不过数据没有卡我们罢了
代码都快200行了，题解才100出头。
自认为码风良好
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define mp make_pair
#define fo(i , x , y) for(int i = x ; i <= y ; i++)
#define go(i , x , y) for(int i = x ; i >= y ; i--)
using namespace std;
const int maxn = 300000;
int n , q;
string s;
struct node{
int pre , suf;
};
struct Segment_Tree{
private:
int cnt , ls[maxn * 2 + 5] , rs[maxn * 2 + 5];
node t[maxn * 2 + 5];
void modify(int f , int v1 , int l , int r , int k){
if(f == 1) t[k].pre = v1;
else t[k].suf = v1;
}
void pushdown(int l , int r , int k){
int mid = (l + r) / 2;
if(t[k].pre != 0){
modify(1 , t[k].pre , l , mid , ls[k]);
modify(1 , t[k].pre , mid + 1 , r , rs[k]);
t[k].pre = 0;
}
if(t[k].suf != 0){
modify(2 , t[k].suf , l , mid , ls[k]);
modify(2 , t[k].suf , mid + 1 , r , rs[k]);
t[k].suf = 0;
}
}
public:
int build(int l , int r){
int k = ++cnt;
if(l == r){
t[k].pre = t[k].suf = l;
return k;
}
t[k].pre = t[k].suf = 0;
int mid = (l + r) / 2;
ls[k] = build(l , mid);
rs[k] = build(mid + 1 , r);
return k;
}
void update(int L , int R , int f , int v1 , int l , int r , int k){
if(L > R) return;
if(L <= l and r <= R){
modify(f , v1 , l , r , k);
return;
}
pushdown(l , r , k);
int mid = (l + r) / 2;
if(L <= mid) update(L , R , f , v1 , l , mid , ls[k]);
if(mid + 1 <= R) update(L , R , f , v1 , mid + 1 , r , rs[k]);
}
node query(int x , int l , int r , int k){
if(l == r) return t[k];
pushdown(l , r , k);
int mid = (l + r) / 2;
if(x <= mid) return query(x , l , mid , ls[k]);
else return query(x , mid + 1 , r , rs[k]);
}
}tr;
struct Segment_Tree2{
private:
int cnt , ls[maxn * 80] , rs[maxn * 80];
long long t[maxn * 80];
public:
int build(int l , int r){
int k = ++cnt;
t[k] = 0;
return k;
}
void update(int x , int v1 , int l , int r , int k){
if(l == r){
t[k] += v1;
return;
}
int mid = (l + r) / 2;
if(x <= mid){
if(ls[k] == 0) ls[k] = build(l , mid);
update(x , v1 , l , mid , ls[k]);
}
else{
if(rs[k] == 0) rs[k] = build(mid + 1 , r);
update(x , v1 , mid + 1 , r , rs[k]);
}
t[k] = t[ls[k]] + t[rs[k]];
}
long long query(int L , int R , int l , int r , int k){
if(k == 0) return 0;
if(L <= l and r <= R) return t[k];
int mid = (l + r) / 2;
if(L <= mid){
long long ans = query(L , R , l , mid , ls[k]);
if(mid + 1 <= R) return ans + query(L , R , mid + 1 , r , rs[k]);
else return ans;
}
else return query(L , R , mid + 1 , r , rs[k]);
}
}tr2;
struct Fenwick_Tree{
private:
int rt[maxn + 5];
int lowbit(int x){
return x & -x;
}
public:
void init(){
fo(i , 1 , n + 1) rt[i] = tr2.build(1 , n + 1);
}
void update(int x , int y , int v){
if(x > n + 1 or y > n + 1) return;
for(int i = x ; i <= n + 1 ; i += lowbit(i))
tr2.update(y , v , 1 , n + 1 , rt[i]);
}
int query(int x , int l , int r){
int ans = 0;
for(int i = x ; i ; i -= lowbit(i))
ans += tr2.query(l , r , 1 , n + 1 , rt[i]);
return ans;
}
}tr3;
void connect(int i , int t){ // connect road between i and i + 1
int l = tr.query(i , 1 , n + 1 , 1).pre;
int r = tr.query(i + 1 , 1 , n + 1 , 1).suf;
tr.update(l , r , 1 , l , 1 , n + 1 , 1);
tr.update(l , r , 2 , r , 1 , n + 1 , 1);
int v = q - t;
tr3.update(i + 1 , r + 1 , v);
tr3.update(i + 1 , i + 1 , -v);
tr3.update(l , r + 1 , -v);
tr3.update(l , i + 1 , v);
}
void erase(int i , int t){ // erase road between i and i + 1
int l = tr.query(i , 1 , n + 1 , 1).pre;
int r = tr.query(i + 1 , 1 , n + 1 , 1).suf;
tr.update(l , i , 2 , i , 1 , n + 1 , 1);
tr.update(i + 1 , r , 1 , i + 1 , 1 , n + 1 , 1);
int v = t - q;
tr3.update(i + 1 , r + 1 , v);
tr3.update(i + 1 , i + 1 , -v);
tr3.update(l , r + 1 , -v);
tr3.update(l , i + 1 , v);
}
long long query(int a , int b , int t){
long long ans = tr3.query(a , 1 , b);
if(tr.query(a , 1 , n + 1 , 1).pre == tr.query(b , 1 , n + 1 , 1).pre) ans -= q - t;
return ans;
}
int main(){
ios :: sync_with_stdio(0) , cin.tie(0) , cout.tie(0);
// freopen(".in" , "r" , stdin);
// freopen(".out" , "w" , stdout);
cin >> n >> q >> s;
s = " " + s;
tr.build(1 , n + 1);
tr3.init();
fo(i , 1 , n){
if(s[i] == '0') continue;
connect(i , 0);
}
fo(t , 1 , q){
string op;
cin >> op;
if(op == "toggle"){
int i;
cin >> i;
if(tr.query(i , 1 , n + 1 , 1).pre != tr.query(i + 1 , 1 , n + 1 , 1).pre)
connect(i , t);
else erase(i , t);
}
else{
int a , b;
cin >> a >> b;
cout << query(a , b , t) << "\n";
}
}
}