제출 #1275441

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1275441		g4yuhg	가로등 (APIO19_street_lamps)	C++20	100 / 100	2931 ms	176040 KiB

street_lamps

//Huyduocdithitp
#include<bits/stdc++.h>
typedef int ll;
#define endl '\n'
#define fi first
#define se second
#define pii pair<ll, ll>
#define N 300005
using namespace std;

// (x, y) bieu thi: thoi gian x -> y di duoc toi nhau
// khi merge (x, i) va (i + 1, y), cac diem u v ma x <= u <= i, i + 1 <= v <= y duoc tang len 1 doan q - t1, de luc sau cong lai t2 - q => t2 - t1 (xet rieng truong hop van con merge)
// => update len bit2d hcn: x, i + 1, i, y

// cong thuc update hcn, truy van diem

struct QR {
	ll tt, i, a, b;
} qr[N];

ll n, q;

vector<ll> node[N], bit[N];

void fake_upd(ll x, ll y) {
	while (x <= n) {
		node[x].push_back(y);
		x += x & (-x);
	}
}

void fake_get(ll x, ll y) {
	while (x > 0) {
		node[x].push_back(y);
		x -= x & (-x);
	}
}

void upd(ll x, ll yy, ll val) {
	while (x <= n) {
		for (int y = lower_bound(node[x].begin(), node[x].end(), yy) - node[x].begin() + 1; y <= node[x].size(); y += y & (-y)) {
			bit[x][y - 1] += val;
		}
		x += x & (-x);
	}
}

ll get(ll x, ll yy) {
	ll ans = 0;
	while (x > 0) {
		for (int y = lower_bound(node[x].begin(), node[x].end(), yy) - node[x].begin() + 1; y > 0; y -= y & (-y)) {
			ans += bit[x][y - 1];
		}
		x -= x & (-x);
	}
	return ans;
}

void fake_add(ll x, ll y, ll u, ll v) {
	fake_upd(x, y);
	fake_upd(x, v + 1);
	fake_upd(u + 1, y);
	fake_upd(u + 1, v + 1);
}

void add(ll x, ll y, ll u, ll v, ll val) {
	upd(x, y, val);
	upd(x, v + 1, -val);
	upd(u + 1, y, -val);
	upd(u + 1, v + 1, val);
}

bool bat[N], bat1[N];

ll L[N], R[N];

void pre() {
	set<pii> s;
	for (int i = 1; i <= n; i ++) { // n da ++
		s.insert({i, i});
		L[i] = i, R[i] = i;
	}
	for (int i = 1; i < n; i ++) {
		if (bat[i]) {
			ll id = i;
			auto it1 = s.lower_bound({id + 1, id + 1});
			auto it2 = it1;
			it1 -- ;
			pii xoa1 = *it1, xoa2 = *it2;
			s.erase(xoa1); s.erase(xoa2);
			s.insert({xoa1.fi, xoa2.se});
			fake_add(xoa1.fi, i + 1, i, xoa2.se);
		}
	}
	for (int i = 1; i <= q; i ++) {
		string tt;
		cin >> tt;
		if (tt == "toggle") {
			ll id; cin >> id;
			qr[i].tt = 1, qr[i].i = id;
			if (bat[id] == 0) {
				// bat no len, ghep thang id voi id + 1
				auto it1 = s.lower_bound({id + 1, 0});
				auto it2 = it1;
				it1 -- ;
				ll x = (*it1).fi;
				ll y = (*it2).se;
				pii xoa1 = *it1, xoa2 = *it2;
				s.erase(xoa1); s.erase(xoa2);
				s.insert({x, y});
				fake_add(x, id + 1, id, y);
			}
			else {
				// tat no di
				auto it = s.lower_bound({id + 1, 0});
				it -- ;
				pii xoa = *it;
				ll x = xoa.fi, y = xoa.se;
				s.erase(xoa);
				s.insert({x, id});
				s.insert({id + 1, y});
				fake_add(x, id + 1, id, y);
			}
			bat[id] = 1 - bat[id];
		}
		else {
			ll a, b; cin >> a >> b;
			qr[i].tt = 2, qr[i].a = a, qr[i].b = b;
			fake_get(a, b);
		}
	}
	for (int i = 1; i <= n; i ++) {
		sort(node[i].begin(), node[i].end());
		node[i].resize(unique(node[i].begin(), node[i].end()) - node[i].begin());
		bit[i].resize((ll)node[i].size(), (ll)0);
	}
}

void solve() {
	set<pii> s;
	for (int i = 1; i <= n; i ++) { // n da ++
		s.insert({i, i});
		bat[i] = bat1[i];
	}
	for (int i = 1; i < n; i ++) {
		if (bat[i]) {
			ll id = i;
			auto it1 = s.lower_bound({id + 1, id + 1});
			auto it2 = it1;
			it1 -- ;
			pii xoa1 = *it1, xoa2 = *it2;
			s.erase(xoa1); s.erase(xoa2);
			s.insert({xoa1.fi, xoa2.se});
			add(xoa1.fi, i + 1, i, xoa2.se, q - 0);
		}
	}
	/*for (auto it : s) {
		cout << it.fi << " " << it.se << endl;
	}*/
	for (int i = 1; i <= q; i ++) {
		if (qr[i].tt == 1) {
			ll id;
			id = qr[i].i;
			if (bat[id] == 0) {
				// bat no len, ghep thang id voi id + 1
				auto it1 = s.lower_bound({id + 1, 0});
				auto it2 = it1;
				it1 -- ;
				ll x = (*it1).fi;
				ll y = (*it2).se;
				pii xoa1 = *it1, xoa2 = *it2;
				s.erase(xoa1); s.erase(xoa2);
				s.insert({x, y});
				//fake_add(x, id + 1, id, y);
				add(x, id + 1, id, y, q - i); // Q - t
			}
			else {
				// tat no di
				auto it = s.lower_bound({id + 1, 0});
				it -- ;
				pii xoa = *it;
				ll x = xoa.fi, y = xoa.se;
				s.erase(xoa);
				s.insert({x, id});
				s.insert({id + 1, y});
				//fake_add(x, id + 1, id, y);
				add(x, id + 1, id, y, i - q);
			}
			bat[id] = 1 - bat[id];
		}
		else {
			ll a, b;
			a = qr[i].a, b = qr[i].b;
			if (a == b) {
                cout << i << endl;
                continue;
			}
			ll x = get(a, b);
			auto it1 = s.lower_bound({b, b});
			it1 -- ;
			pii xoa = *it1;
			if (xoa.fi <= a && b <= xoa.se) {
				x -= q - i;
			}
			cout << x << endl;
		}
	}
}

signed main() {
    //freopen("test.inp", "r", stdin);
    //freopen("test.out", "w", stdout);
    ios_base::sync_with_stdio(0); cin.tie(0);
    cout.tie(0);

    cin >> n >> q;
    for (int i = 1; i <= n; i ++) {
    	char u; cin >> u;
    	if (u == '0') bat[i] = 0;
    	else bat[i] = 1;
    	bat1[i] = bat[i];
    }
    n ++ ;

    pre();

    solve();

}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20