#include <bits/stdc++.h>
using namespace std;
template<class T, class U>
void ckmin(T &a, U b)
{
if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
if (a < b) a = b;
}
#define y1 orz
#define y2 tmw
#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
#define MAXN 351313
#define INF 1000000007
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
int N, Q;
bitset<MAXN> state;
pii quer[MAXN];
vi pts[MAXN];
vi ptseg[3 * MAXN], fen[3 * MAXN];
map<int, int> lst[MAXN];
set<int> lts, rts;
int ans;
int seg[3 * MAXN];
void build(int w, int L, int R)
{
if (L == R)
{
swap(ptseg[w], pts[L]);
fen[w].resize(SZ(ptseg[w]) + 2);
return;
}
int mid = (L + R) >> 1;
build(w << 1, L, mid);
build(w << 1 | 1, mid + 1, R);
int iter = 0;
FOR(i, 0, SZ(ptseg[w << 1]))
{
while(iter < SZ(ptseg[w << 1 | 1]) && ptseg[w << 1 | 1][iter] <= ptseg[w << 1][i])
{
if (ptseg[w << 1 | 1][iter] != ptseg[w << 1][i])
{
ptseg[w].PB(ptseg[w << 1 | 1][iter]);
}
iter++;
}
ptseg[w].PB(ptseg[w << 1][i]);
}
while(iter < SZ(ptseg[w << 1 | 1]))
{
ptseg[w].PB(ptseg[w << 1 | 1][iter]);
iter++;
}
fen[w].resize(SZ(ptseg[w]) + 2);
return;
}
void upd(int w, int L, int R, int a, int x, int v)
{
// if (w == 1)
// {
// cerr << "UPDATE " << a << ',' << x << "with " << v << endl;
// }
int idx = LB(ALL(ptseg[w]), x) - ptseg[w].begin();
for (int e = idx + 1; e < SZ(fen[w]); e += e & (-e))
{
fen[w][e] += v;
}
if (L == R) return;
int mid = (L + R) >> 1;
if (a <= mid) upd(w << 1, L, mid, a, x, v);
else upd(w << 1 | 1, mid + 1, R, a, x, v);
}
int qry(int w, int L, int R, int a, int b, int y1, int y2)
{
// if (w == 1)
// {
// cerr << "QUERY " << a << ' ' << b << ' ' << y1 << ' ' << y2 << endl;
// }
////cerr << "INSIDE " << L << ' ' << R << endl;
////cerr << endl;
if (a <= L && R <= b)
{
int res = 0;
int idx = UB(ALL(ptseg[w]), y2) - ptseg[w].begin() - 1;
for (int e = idx + 1; e; e -= e & (-e))
{
////cerr << "PLUS " << fen[w][e] << endl;
res += fen[w][e];
}
idx = UB(ALL(ptseg[w]), y1 - 1) - ptseg[w].begin() - 1;
for (int e = idx + 1; e; e -= e & (-e))
{
////cerr << "MINUS " << fen[w][e] << endl;
res -= fen[w][e];
}
return res;
}
int mid = (L + R) >> 1, res = 0;
if (a <= mid) res += qry(w << 1, L, mid, a, b, y1, y2);
else res += qry(w << 1 | 1, mid + 1, R, a, b, y1, y2);
return res;
}
void update(int w, int L, int R, int a, int t)
{
if (L == R)
{
seg[w] = t;
return;
}
int mid = (L + R) >> 1;
if (a <= mid)
{
update(w << 1, L, mid, a, t);
}
else
{
update(w << 1 | 1, mid + 1, R, a, t);
}
seg[w] = max(seg[w << 1], seg[w << 1 | 1]);
}
int query(int w, int L, int R, int a, int b)
{
if (a <= L && R <= b)
{
return seg[w];
}
int mid = (L + R) >> 1, res = -INF;
if (a <= mid)
{
ckmax(res, query(w << 1, L, mid, a, b));
}
if (mid < b)
{
ckmax(res, query(w << 1 | 1, mid + 1, R, a, b));
}
return res;
}
void del(int idx, int t, bool flag)
{
// cerr << "DEL " << idx << ' ' << t << ' ' << flag << endl;
int lt = *prev(lts.UB(idx)), rt = *rts.LB(idx);
lts.erase(lt); rts.erase(rt);
// cerr << "HAHAHA " << lt << ' ' << rt << endl;
if (flag)
{
//cerr << "FIRST OK TIME " << lst[lt][rt] << endl;
upd(1, 0, N - 1, lt, rt, t - lst[lt][rt]);
//update(lt, rt) with t - ls.
}
else
{
pts[lt].PB(rt);
}
if (lt != idx)
{
lst[lt].clear();
lst[lt][idx - 1] = t;
lts.insert(lt);
rts.insert(idx - 1);
}
if (rt != idx)
{
lst[idx + 1].clear();
lst[idx + 1][rt] = t;
lts.insert(idx + 1);
rts.insert(rt);
}
if (flag)
{
update(1, 0, N - 1, idx, Q + 1);
}
}
void ins(int idx, int t, bool flag)
{
// cerr << "INS " << idx << ' ' << t << ' ' << flag << endl;
if (rts.find(idx - 1) != rts.end() && lts.find(idx + 1) != lts.end())
{
int lt = *prev(lts.UB(idx)), rt = *rts.LB(idx);
rts.erase(idx - 1);
lts.erase(idx + 1);
if (flag)
{
upd(1, 0, N - 1, lt, idx - 1, t - lst[lt][idx - 1]);
upd(1, 0, N - 1, idx + 1, rt, t - lst[idx + 1][rt]);
//update(lt, idx - 1) with t - ls
//update(idx + 1, rt) with t - ls
lst[lt].clear();
lst[lt][rt] = t;
}
else
{
pts[lt].PB(idx - 1);
pts[idx + 1].PB(rt);
}
}
else if (rts.find(idx - 1) != rts.end())
{
int lt = *prev(lts.UB(idx));
rts.erase(idx - 1);
rts.insert(idx);
// cerr << "erase " << idx - 1 << " insert " << idx << endl;
if (flag)
{
upd(1, 0, N - 1, lt, idx - 1, t - lst[lt][idx - 1]);
//update(lt, idx - 1) with t - ls.
lst[lt].clear();
lst[lt][idx] = t;
}
else
{
pts[lt].PB(idx - 1);
}
}
else if (lts.find(idx + 1) != lts.end())
{
int rt = *rts.LB(idx);
lts.erase(idx + 1);
lts.insert(idx);
if (flag)
{
upd(1, 0, N - 1, idx + 1, rt, t - lst[idx + 1][rt]);
//update(idx + 1, rt) with t - ls.
lst[idx].clear();
lst[idx][rt] = t;
}
else
{
pts[idx + 1].PB(rt);
}
}
else
{
lts.insert(idx);
rts.insert(idx);
lst[idx].clear();
lst[idx][idx] = t;
}
if (flag)
{
update(1, 0, N - 1, idx, t);
}
}
int32_t main()
{
ios_base::sync_with_stdio(false); cin.tie(0);
cout << fixed << setprecision(12);
////cerr << fixed << setprecision(4);
cin >> N >> Q;
string temps; cin >> temps;
FOR(i, 0, N)
{
state[i] = (temps[i] == '1');
if (state[i])
{
update(1, 0, N - 1, i, -1);
}
else
{
update(1, 0, N - 1, i, Q + 1);
}
}
FOR(i, 0, N)
{
if (state[i] && (i == 0 || !state[i - 1])) lts.insert(i);
if (state[i] && (i == N - 1 || !state[i + 1])) rts.insert(i);
}
for (auto it = lts.begin(), jt = rts.begin(); it != lts.end(); it++, jt++)
{
lst[*it][*jt] = -1;
}
FOR(i, 0, Q)
{
cin >> temps;
int x, y;
if (temps[0] == 't')
{
cin >> x; x--;
quer[i] = {-1, x};
}
else
{
cin >> x >> y; x--; y -= 2;
quer[i] = {x, y};
}
}
FOR(i, 0, Q)
{
if (quer[i].fi == -1)
{
int idx = quer[i].se;
if (!state[idx])
{
ins(idx, i, 0);
}
else
{
del(idx, i, 0);
}
state[idx] = state[idx] ^ 1;
}
}
FOR(i, 0, Q)
{
if (quer[i].fi == -1)
{
int idx = quer[i].se;
state[idx] = state[idx] ^ 1;
}
}
FOR(i, 0, N)
{
sort(ALL(pts[i]));
pts[i].erase(unique(ALL(pts[i])), pts[i].end());
// cerr << "IN PTS " << i << ":";
// for (int x : pts[i])
// {
// cerr << ' ' << x;
// }
// cerr << endl;
}
build(1, 0, N - 1);
// ////cerr << "YES\n";
lts.clear(); rts.clear();
FOR(i, 0, N)
{
if (state[i] && (i == 0 || !state[i - 1])) lts.insert(i);
if (state[i] && (i == N - 1 || !state[i + 1])) rts.insert(i);
}
// ////cerr << "ALIVE\n";
FOR(i, 0, Q)
{
if (quer[i].fi == -1)
{
int idx = quer[i].se;
if (!state[idx])
{
ins(idx, i, 1);
}
else
{
del(idx, i, 1);
}
state[idx] = state[idx] ^ 1;
}
else
{
int lt = quer[i].fi, rt = quer[i].se;
// //////cerr << "ANSWER " << lt << ' ' << rt << endl;
ans = qry(1, 0, N - 1, 0, lt, rt, N - 1);
//query rectangle of 0...lt rt....N-1
int t = query(1, 0, N - 1, lt, rt);
// cerr << "T = " << t << endl;
if (t < i)
{
int blah = *prev(lts.LB(lt));
int pt = lst[blah].begin() -> se;
// cerr << "PEQ " << i - t << endl;
ans += (i - pt);
}
cout << ans << '\n';
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
69 ms |
74616 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
405 ms |
81484 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
72 ms |
74872 KB |
Output is correct |
| 2 |
Incorrect |
75 ms |
74876 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
72 ms |
74872 KB |
Output is correct |
| 2 |
Incorrect |
72 ms |
74820 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
69 ms |
74616 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
