---
tags: APIO
---
# APIO 2019-C 街灯 (Street Lamps)

## 問題文

https://apio2019.ru/upload/statements/Japanese.pdf
https://oj.uz/problem/view/APIO19_street_lamps

街灯が $n$ 個あり、点いていたりいなかったりします。 タクシーは 街灯 $[a,b)$ が点いているとき、区間 $[a,b)$ を運転できます。
時刻 $1 \dots q$ にクエリが来るので、処理してください。
- toggle $i$ : 街灯 $i$ の状態を反転
- query $a, b$ : 時刻 0 から今までのうち、区間 $[a,b)$ を運転できた時間を出力

TL 5s で $1 ≤ n, q ≤ 300000$

## 考察

query を2次元平面の点と見て、そこに (現在移動できるか, 最後に変わった時間) を持たせると、 toggle は矩形範囲への変更になる。
矩形変更1点取得は、kD-Treeで $O(\sqrt{N})$ でできる。(おそらく今回のは2次元セグ木にならない)
kD-Tree は脳死でも組めるのでおすすめ。
ただし今回のは toggle の合成がかなり面倒。

## 実装

計算量は $O((N+Q)\sqrt{N})$ くらいで、 2809ms

https://oj.uz/submission/210007

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int INF = 0x3fffffff;
#define rep(n) for(int i=0;i<n;++i)
#define each(i,...) for(auto&& i:__VA_ARGS__)
#define all(i) begin(i),end(i)
#define Uniq(a) sort(all(a));a.erase(unique(all(a)),end(a))
template<class T, class U> bool chmin(T& a, const U& b){ if(a > b){ a = b; return 1; } return 0; }
template<class T, class U> bool chmax(T& a, const U& b){ if(a < b){ a = b; return 1; } return 0; }
 
 
 
struct Lazy{
    int type;
    int first, last, cnt;
    void operator+=(const Lazy& b){ // toggle の合成
        if(!type){
            *this = b;
            return;
        }
        cnt += b.cnt;
        if(type == 2) cnt += b.first - last;
        last = b.last;
        type = b.type;
    }
};
struct kdTree{
    kdTree *l = nullptr, *r = nullptr;
    Lazy val = {0, 0, 0, 0};
    int xmin = INF, xmax = -INF, ymin = INF, ymax = -INF;
    kdTree(vector<pii>::iterator from, vector<pii>::iterator to, bool divx = false){
        for(auto p = from; p != to; p++){
            auto& i = *p;
            chmin(xmin, i.first);
            chmax(xmax, i.first);
            chmin(ymin, i.second);
            chmax(ymax, i.second);
        }
        if(to - from == 1) return;
        auto p = from + (to - from) / 2;
        if(divx) nth_element(from, p, to, [](pii a, pii b){ return a.first < b.first; });
        else nth_element(from, p, to, [](pii a, pii b){ return a.second < b.second; });
        l = new kdTree(from, p, !divx);
        r = new kdTree(p, to, !divx);
    }
    void push(){
        if(!l) return;
        if(!val.type) return;
        l->val += val;
        r->val += val;
        val = {0, 0, 0, 0};
    }
    void query(int x1, int x2, int y1, int y2, const Lazy& x){ // [x1, x2] && [y1, y2]
        if(xmax < x1 || x2 < xmin || ymax < y1 || y2 < ymin) return;
        if(x1 <= xmin && xmax <= x2 && y1 <= ymin && ymax <= y2){ // <- ここだけバグらせやすいので注意
            val += x;
            return;
        }
        push();
        l->query(x1, x2, y1, y2, x);
        r->query(x1, x2, y1, y2, x);
    }
    int get(int x, int y, int time){ // l の範囲内 && r の範囲内 になることがあってこうなっているが、これは構築部分を変えれば回避できる
        if(!l) return val.cnt + (val.type == 2 ? time - val.last : 0);
        push();
        if(l->xmin <= x && x <= l->xmax && l->ymin <= y && y <= l->ymax){
            int ans = l->get(x, y, time);
            if(ans != -1) return ans;
        }
        if(r->xmin <= x && x <= r->xmax && r->ymin <= y && y <= r->ymax){
            return r->get(x, y, time);
        }
        return -1;
    }
};
int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;
    vector<pii> a;
    vector<pair<char, pii>> query(q);
    each(i, query){
        string s;
        cin >> s;
        i.first = s[0];
        int x, y = 2;
        cin >> x;
        if(i.first == 'q') cin >> y;
        x--; y -= 2;
        i.second = {x, y};
        if(i.first == 'q') a.emplace_back(x, y);
    }
    Uniq(a);
    kdTree tree(all(a));
    set<int> dark = {-1, n};
    tree.query(0, n, 0, n, {2, 0, 0, 0});
    rep(n) if(s[i] == '0'){
        auto p = dark.insert(i).first;
        int x1 = *prev(p) + 1, x2 = *next(p) - 1;
        tree.query(x1, i, i, x2, {1, 0, 0, 0});
    }
    rep(q){
        char c = query[i].first;
        int x, y, time = i + 1;
        tie(x, y) = query[i].second;
        if(c == 't'){
            s[x] ^= 1;
            if(s[x] == '1'){
                auto p = dark.find(x);
                int x1 = *prev(p) + 1, x2 = *next(p) - 1;
                tree.query(x1, x, x, x2, {2, time, time, 0});
                dark.erase(p);
            }
            else{
                auto p = dark.insert(x).first;
                int x1 = *prev(p) + 1, x2 = *next(p) - 1;
                tree.query(x1, x, x, x2, {1, time, time, 0});
            }
        }
        else{
            cout << tree.get(x, y, time) << '\n';
        }
    }
}