제출 #733500

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
733500		Username4132	가로등 (APIO19_street_lamps)	C++14	0 / 100	140 ms	101696 KiB

street_lamps

#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<cassert>
using namespace std;

using ll = long long;
using pii = pair<int, int>;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define PB push_back
#define F first
#define S second

const int MAXN=300010;
int n, m;
string str;


ll sum(vector<ll>& bit, int r){
    ll ret=0;
    for(; r>=0; r=(r&(r+1))-1) ret+=bit[r];
    return ret;
}

void add(vector<ll>& bit, int r, int delta){
    for(; r<(int)bit.size(); r=r|(r+1)) bit[r]+=delta;
}

void add(vector<ll>& bit, int l, int r, int delta){
    add(bit, l, delta);
    add(bit, r, -delta);
}

struct fen{
    vector<int> nd;
    vector<ll> e, t;
    void su(bool mode, int bl, int br, int delta){
        int l = lower_bound(nd.begin(), nd.end(), bl) - nd.begin();
        int r = lower_bound(nd.begin(), nd.end(), br) - nd.begin();
        if(mode) add(e, l, r, delta);
        else add(t, l, r, delta);
    }
};

set<int> tur;
bool sw[MAXN];
fen tr[MAXN];

fen combine(fen a, fen b){
    fen ret;
    int sz=a.nd.size()+b.nd.size();
    ret.nd.resize(sz), ret.e.resize(sz), ret.t.resize(sz);
    merge(a.nd.begin(), a.nd.end(), b.nd.begin(), b.nd.end(), ret.nd.begin());
    return ret;
}

void update(int l, int r, bool mode, int bl, int br, int tm){
    for(l+=n, r+=n; l<r; l>>=1, r>>=1){
        if(l&1) tr[l++].su(mode, bl, br, tm);
        if(r&1) tr[--r].su(mode, bl, br, tm);
    }
}

void toggle(int ind, int tm){
    if(sw[ind]){
        sw[ind]=false;
        auto itr=tur.find(ind), nx=next(itr);
        int start = itr==tur.begin()? 0 : ((*prev(itr))+1);
        int en = ind+1;
        int bnd = nx==tur.end()? n : ((*nx)+1);
        tur.erase(itr);
        update(start, en, 0, en, bnd, tm);

    }
    else{
        sw[ind]=true;


    }
}

ll query(int l, int r, int tm){
    ll ret=0;
    l+=n;
    while(l>0){
        auto itr=lower_bound(tr[l].nd.begin(), tr[l].nd.end(), r);
        assert(itr!=tr[l].nd.end() && *itr==r);
        int pos=itr-tr[l].nd.begin();
        ret+=sum(tr[l].e, pos);
        ret-=sum(tr[l].t, pos);
        l>>=1;
    }

    auto itr=tur.lower_bound(l);
    if(itr==tur.end() || *itr>=r){
        ret+=tm;
    }
    return ret;
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m >> str;
    ++n;

    vector<pii> qrs(m);

    forn(i, m){
        string type;
        cin >> type;
        if(type[0]=='q'){
            int a, b; cin >> a >> b; --a, --b;
            qrs[i]={a, b};
            tr[n+a].nd.PB(b);
        }
        else{
            int a; cin >> a; --a;
            qrs[i]={a, -1};
        }
    }

    forn(i, n){
        sort(tr[n+i].nd.begin(), tr[n+i].nd.end());
        tr[n+i].e.resize(tr[n+i].nd.size());
        tr[n+i].t.resize(tr[n+i].nd.size());
    }

    for(int i=n-1; i>0; --i) tr[i]=combine(tr[i<<1], tr[i<<1|1]);

    forn(i, n-1) tur.insert(i), sw[i]=true;
    forn(i, n-1) if(str[i]=='1') toggle(i, -1);
    forn(i, m){
        if(qrs[i].S==-1){
            toggle(qrs[i].F, i);
        }
        else{
            ll ans = query(qrs[i].F, qrs[i].S, i);
            cout << ans << '\n';
        }
    }


}

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