#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define inf 1e18
#define fi first
#define se second
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define endl '\n'
#define pi 3.14159265359
#define TASKNAME "streetlamp"
using namespace std;
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
/**
Street lamp:
Có n trạm dừng kết nối n + 1 cái stop.
ta biết trạng thái của cái stop
Ta có q truy vấn:
- query a b: Từ 1 đến i, ta, tổng các thời điểm mà ta có thể đi từ a b
- toggle i: lật ngược vị trí i
subtask 1: n <= 100, q <= 100. Chạy n * q^2.
subtask 2: b = a + 1.
Tức là ta chỉ quan tâm vị trí i được bật bao nhiêu lần.
cái này bỏ vào prefix sum.
subtask 3: Khi bật nút i, nó sẽ luôn bật.
Nó là bài toán dsu điển hình, tức là 2 đỉnh sẽ không bao giờ bị disconnect.
subtask 4:
Ta toggle trước xong mới đến các truy vấn.
Giả sử ta dsu rollback, khi ta thêm 1 cạnh vào, nó
sẽ liên kết các tplt bên trong đó.
Giả sử nó nối đoạn [1...3] với [4..5] thì ta thêm hình chữ nhật [1...3], [4...5]
với trọng số là thời gian t.
Khi này ta sẽ tính offline bằng sweepline. Giả sử ta cần truy vấn a, b: thì ta chỉ cần truy vấn đoạn [a, b].
Ta có n log n sự kiện thì có tối đa n log n hình chữ nhật,
subtask 5:
Bây giờ ta cần phải xử lý online. Làm thế nào cơ chứ.
Nếu ta cắm BIT2D vào thì nó cũng vẫn sẽ là N log ^ 3 N.
Ta chia các hcn thành 2 loại:
- Đã kết thúc
- Còn thời gian.
**/
const int MAXN = 3e5 + 9;
int n, q, u, v;
char lamp[MAXN];
struct query{
string type;
int l, r, u;
} Query[MAXN];
struct DSU{
struct DSUnode{
int par;
int sz;
int mn;
int mx;
};
vector<DSUnode> D;
vector<array<int, 6>> changes;
int small_to_large, path_compression, roll_back;
DSU(int sz = 0, int _small_to_large = 1, int _path_compression = 1, int _roll_back = 0){
D.resize(sz + 9);
small_to_large = _small_to_large;
path_compression = _path_compression;
roll_back = _roll_back;
FOR(i, 0, D.size() - 1){
D[i].par = i;
D[i].sz = 1;
D[i].mn = D[i].mx = i;
}
}
void rollback(){
if (changes.size() == 0) return;
array<int, 6> tp = changes.back();
int u = tp[0];
int v = tp[1];
D[u].sz -= D[v].sz;
D[v].par = v;
D[u].mn = tp[2], D[u].mx = tp[3];
D[v].mn = tp[4], D[v].mx = tp[5];
changes.pop_back();
}
int root(int u){
if (D[u].par == u) return u;
else {
int p = root(D[u].par);
if (path_compression) D[u].par = p;
return p;
}
}
bool unite(int u, int v){
u = root(u);
v = root(v);
if (u != v){
if (small_to_large and D[u].sz < D[v].sz) swap(u, v);
D[u].sz += D[v].sz;
D[v].par = u;
if (roll_back) changes.pb({u, v, D[u].mn, D[u].mx, D[v].mn, D[v].mx});;
D[u].mx = max(D[u].mx, D[v].mx);
D[u].mn = min(D[u].mn, D[v].mn);
return true;
}
return false;
}
};
namespace subtask1{
bool check(){
return n <= 100 and q <= 100;
}
DSU timelineDSU[103];
void solve(){
FOR(i, 1, q){
timelineDSU[i] = DSU(n + 1);
FOR(j, 1, n){
if (lamp[j] == '1') {
timelineDSU[i].unite(j, j + 1);
}
}
if (Query[i].type == "toggle"){
int u = Query[i].u;
lamp[u] = ((lamp[u] == '0') ? '1' : '0');
}
else{
int ans = 0;
FOR(j, 1, i){
if (timelineDSU[j].root(Query[i].l) == timelineDSU[j].root(Query[i].r)) {
ans++;
}
}
cout << ans << endl;
}
}
}
}
namespace subtask2{
bool check(){
FOR(i, 1, q){
if (Query[i].type == "query" and Query[i].l != Query[i].r - 1) return false;
}
return true;
}
int pre[300003], lastTime[MAXN];
void solve(){
FOR(i, 1, n){
pre[i] = 0;
if (lamp[i] == '1') lastTime[i] = 1;
}
FOR(i, 1, q){
if (Query[i].type == "toggle"){
int u = Query[i].u;
if (lamp[u] == '1') {
pre[u] += i - lastTime[u] + 1;
lastTime[u] = 0;
lamp[u] = '0';
}
else{
lastTime[u] = i + 1;
lamp[u] = '1';
}
}
if (Query[i].type == "query"){
int ans = pre[Query[i].l];
if (lamp[Query[i].l] == '1'){
ans += i - lastTime[Query[i].l] + 1;
}
cout << ans << endl;
}
}
}
}
namespace subtask3{
char tmp[300005];
bool check(){
FOR(i, 1, n){
tmp[i] = lamp[i];
}
FOR(i, 1, q){
if (Query[i].type == "toggle" and tmp[Query[i].u] == '1') return false;
if (Query[i].type == "toggle") tmp[Query[i].u] = '1';
}
return true;
}
/**
Voi 2 dinh a va b, ta can tim thoi gian dau tien ma hai thang do ket hop lam 1. Cái này có thể giải bằng
chặt nhị phân song song.
Dùng reachability Tree.
**/
vector<int> reachability[MAXN * 2];
int edgeTime[MAXN * 2];
int P[22][MAXN * 2], depth[MAXN * 2];
void dfs(int u, int p){
P[0][u] = p;
for(auto v: reachability[u]){
depth[v] = depth[u] + 1;
dfs(v, u);
}
}
int lca(int u, int v){
if (depth[u] < depth[v]) swap(u, v);
FORD(i, 20, 0){
if (P[i][u] != -1 and depth[P[i][u]] >= depth[v]) u = P[i][u];
}
if (u == v) return u;
FORD(i, 20, 0){
if (P[i][u] != -1 and P[i][v] != -1 and P[i][u] != P[i][v]) {
u = P[i][u];
v = P[i][v];
}
}
return P[0][u];
}
void solve(){
int small_to_large = 0;
int path_compression = 1;
int roll_back = 0;
DSU D(2 * n + 9, small_to_large, path_compression, roll_back);
int cntEdge = n + 1;
FOR(i, 1, n){
if (lamp[i] == '1') {
++cntEdge;
edgeTime[cntEdge] = 1;
int r1 = D.root(i);
int r2 = D.root(i + 1);
if (D.unite(cntEdge, r1)){
// cerr << cntEdge << ' ' << r1 << endl;
reachability[cntEdge].pb(r1);
}
if (D.unite(cntEdge, r2)){
// cerr << cntEdge << ' ' << r2 << endl;
reachability[cntEdge].pb(r2);
}
}
}
FOR(i, 1, q){
if (Query[i].type == "toggle"){
int u = Query[i].u;
++cntEdge;
edgeTime[cntEdge] = i + 1;
int r1 = D.root(u);
int r2 = D.root(u + 1);
if (D.unite(cntEdge, r1)){
// cerr << cntEdge << ' ' << r1 << endl;
reachability[cntEdge].pb(r1);
}
if (D.unite(cntEdge, r2)){
// cerr << cntEdge << ' ' << r2 << endl;
reachability[cntEdge].pb(r2);
}
}
}
FORD(i, 2 * n + 3, 1){
if (P[0][i] == 0) dfs(i, -1);
}
FOR(i, 1, 20){
FOR(j, 1, 2 * n + 3){
if (P[i - 1][j] == -1) P[i][j] = -1;
P[i][j] = P[i - 1][P[i - 1][j]];
}
}
FOR(i, 1, q){
int ans = 0;
if (Query[i].type == "query"){
int l = Query[i].l;
int r = Query[i].r;
if (D.root(l) == D.root(r)){
int acs = lca(l, r);
if (i >= edgeTime[acs]) ans += i - edgeTime[acs] + 1;
}
cout << ans << endl;
}
}
}
}
struct BinaryIndexedTree{
vector<int> BIT;
BinaryIndexedTree(int sz = 0){
BIT.resize(sz + 9);
}
void update(int id, int val){
for(int i = id; i < BIT.size(); i += i & (-i)){
BIT[i] += val;
}
}
int get(int id){
int res = 0;
for(int i = id; i > 0; i -= i & (-i)){
res += BIT[i];
}
return res;
}
void updateRange(int l, int r, int val){
update(l, val);
update(r + 1, -val);
}
};
namespace subtask4{
bool check(){
bool alreadyQuery = 0;
FOR(i, 1, q){
if (Query[i].type == "toggle" and alreadyQuery) return false;
if (Query[i].type == "query") alreadyQuery = true;
}
return true;
}
struct rectangle{
int L, R, B, T, val;
rectangle(int _L = 0, int _R = 0, int _B = 0, int _T = 0, int _v = 0){
L = _L;
R = _R;
B = _B;
T = _T;
val = _v;
}
};
vector<rectangle> rect;
vector<iii> points;
struct event{
int x, type, l, r;
event(int _x = 0, int _type = 0, int _l = 0, int _r = 0): x(_x), type(_type), l(_l), r(_r) {}
};
vector<int> valRectangleInclude(vector<rectangle> rect, vector<iii> points){
vector<int> result(points.size());
vector<event> events;
BinaryIndexedTree BIT(300005);
FOR(i, 0, (int) rect.size() - 1){
events.pb(event(rect[i].L, rect[i].val, rect[i].B, rect[i].T));
events.pb(event(rect[i].R + 1,-rect[i].val, rect[i].B, rect[i].T));
// cerr << rect[i].L << ' ' << rect[i].R << ' ' << rect[i].B << ' ' << rect[i].T << ' ' << rect[i].val << endl;
}
FOR(i, 0, (int) points.size() - 1){
// cerr << points[i].fi << ' ' << points[i].se.fi << ' ' << points[i].se.se << endl;
events.pb(event(points[i].se.fi, 0, points[i].fi, points[i].se.se));
}
sort(events.begin(), events.end(), [&](const event &a, const event &b){
return a.x < b.x;
});
for(int i = 0, j = 0; i < events.size(); i = j){
j = i;
// cerr << "X: " << events[i].x << endl;
while(j < events.size() and events[j].x == events[i].x){
if (events[j].type != 0) {
BIT.updateRange(events[j].l, events[j].r, events[j].type);
// cerr << "UPDATE: " << events[j].l << ' ' << events[j].r << ' ' << events[j].type << endl;
}
j++;
}
j = i;
while(j < events.size() and events[j].x == events[i].x){
if (events[j].type == 0) {
// cerr << "GET: " << events[j].x << ' ' << events[j].r << endl;
result[events[j].l] = BIT.get(events[j].r);
}
j++;
}
}
return result;
}
/**
Moi lan ta them canh vao, ta chac no se tao 1 thanh phan lien thong moi, ta chi quan tam rang la
2 doan ma no dang o thoi.
Khi ta add 2 thang vao thi chac chan no se la hai thang tien de tao thanh 2 thang lon hon.
**/
vector<int> dsuRollback[MAXN << 2];
DSU D;
void addEvent(int nn, int l, int r, int u, int v, int e){
if (l >= u and r <= v){
dsuRollback[nn].pb(e);
return;
}
if (l > v or r < u) return;
int mid = (l + r) >> 1;
addEvent(nn << 1, l, mid, u, v, e);
addEvent(nn << 1 | 1, mid + 1, r, u, v, e);
}
void go(int nn, int l, int r){
int sz = D.changes.size();
for(auto p: dsuRollback[nn]){
D.unite(p, p + 1);
int rt = D.root(p);
rect.pb(rectangle(D.D[rt].mn, p, p + 1, D.D[rt].mx, r - l + 1));
}
if (l != r){
int mid = (l + r) >> 1;
go(nn << 1, l, mid);
go(nn << 1 | 1, mid + 1, r);
}
while(D.changes.size() > sz) D.rollback();
}
int lastTime[MAXN];
void solve(){
int startAsking = q + 1;
FOR(i, 1, q){
if (Query[i].type == "query") {
startAsking = i;
break;
}
}
D = DSU(n + 1, 1, 0, 1);
DSU current = DSU(n + 1, 1, 1, 0);
FOR(i, 1, n){
if (lamp[i] == '1') lastTime[i] = 1;
}
FOR(i, 1, startAsking - 1){
int u = Query[i].u;
if (lamp[u] == '1'){
addEvent(1, 1, startAsking, lastTime[u], i, u);
lastTime[u] = 0;
lamp[u] = '0';
}
else{
lamp[u] = '1';
lastTime[u] = i + 1;
}
}
FOR(i, 1, n){
if (lastTime[i] > 0) addEvent(1, 1, startAsking, lastTime[i], startAsking, i);
}
go(1, 1, startAsking);
FOR(i, 1, n){
if (lamp[i] == '1') current.unite(i, i + 1);
}
FOR(i, startAsking, q){
points.pb({i - startAsking, ii(Query[i].l, Query[i].r)});
}
// for(int i = 0; i < rect.size(); i++){
// cerr << rect[i].val << endl;
// }
vector<int> result = valRectangleInclude(rect, points);
FOR(i, startAsking, q){
int l = Query[i].l;
int r = Query[i].r;
if (current.root(l) == current.root(r)){
result[i - startAsking] += i - startAsking;
}
cout << result[i - startAsking] << endl;
}
}
}
main()
{
fast;
if (fopen(TASKNAME".inp","r")){
freopen(TASKNAME".inp","r",stdin);
freopen(TASKNAME".out","w",stdout);
}
cin >> n >> q;
FOR(i, 1, n){
cin >> lamp[i];
}
FOR(i, 1, q){
cin >> Query[i].type;
if (Query[i].type == "toggle"){
cin >> Query[i].u;
}
else if (Query[i].type == "query"){
cin >> Query[i].l >> Query[i].r;
}
}
if (subtask1::check()) return subtask1::solve(), 0;
if (subtask2::check()) return subtask2::solve(), 0;
if (subtask3::check()) return subtask3::solve(), 0;
if (subtask4::check()) return subtask4::solve(), 0;
}
/**
Warning:
Cận lmao
Code imple thiếu case nào không.
Limit.
**/
