LibreOJ 3146. 「APIO2019」路灯

这个显然是要把询问维护成点对的答案。

考虑用 set 维护所谓连通的极大连续段，那么操作显然只会连接两个段或是断开一个段。
同时在矩阵上更新下答案即可。

然后，由于询问问的是有多少个时刻而非当前是否可到达，所以考虑时间轴上差分。
即，若在时刻新增 / 减少了段，则令的矩阵都，意即这个时刻及之后的贡献。

查询的时候，如果这两点还连通，要注意把答案减去，表示当前时刻。
因为时间轴差分并没有考虑到这是在中途询问。

代码：

#include <cstdio>
#include <algorithm>
#include <set>
#define lowbit(x) ((x) & -(x))
using namespace std;
const int N = 3e5;
int n,q;
int a[N + 5];
struct note
{
    int l,r;
    inline bool operator<(const note &o) const
    {
        return l < o.l;
    }
};
set<note> d;
struct node
{
    long long val;
    int ls,rs;
} seg[(N << 6) + 10];
int rt[N + 5];
void update(int l,int r,int k,int &p,int tl,int tr)
{
    static int tot = 0;
    if(!p)
        p = ++tot;
    if(l <= tl && tr <= r)
    {
        seg[p].val += k;
        return ;
    }
    int mid = tl + tr >> 1;
    l <= mid && (update(l,r,k,seg[p].ls,tl,mid),1);
    r > mid && (update(l,r,k,seg[p].rs,mid + 1,tr),1);
}
long long query(int x,int p,int tl,int tr)
{
    if(!p || tl == tr)
        return seg[p].val;
    int mid = tl + tr >> 1;
    return seg[p].val + (x <= mid ? query(x,seg[p].ls,tl,mid) : query(x,seg[p].rs,mid + 1,tr));
}
inline void update(int x,int l,int r,int k)
{
    for(;x <= n + 1;x += lowbit(x))
        update(l,r,k,rt[x],1,n + 1);
}
inline long long query(int x,int y)
{
    long long ret = 0;
    for(;x;x -= lowbit(x))
        ret += query(y,rt[x],1,n + 1);
    return ret;
}
inline void update(int x,int y,int l,int r,int k)
{
    update(x,l,r,k),update(y + 1,l,r,-k);
}
int main()
{
    scanf("%d%d",&n,&q);
    char ch;
    for(register int i = 1;i <= n;++i)
        scanf(" %c",&ch),a[i] = ch ^ '0';
    for(register int i = 1,temp = 1;i <= n + 1;++i)
        if(!a[i])
            d.insert((note){temp,i}),update(temp,i,temp,i,q),temp = i + 1;
    char op[7];
    int x,y;
    for(register int i = 1;i <= q;++i)
    {
        scanf("%s%d",op + 1,&x);
        if(op[1] == 't')
        {
            if(!a[x])
            {
                set<note>::iterator itl = --d.upper_bound((note){x,0});
                set<note>::iterator itr = d.lower_bound((note){x + 1,0});
                int l = itl->l,r = itr->r;
                update(l,x,l,x,i - q),update(x + 1,r,x + 1,r,i - q);
                d.erase(itl),d.erase(itr);
                d.insert((note){l,r});
                update(l,r,l,r,q - i);
            }
            else
            {
                set<note>::iterator it = --d.upper_bound((note){x,0});
                int l = it->l,r = it->r;
                update(l,r,l,r,i - q);
                d.erase(it);
                d.insert((note){l,x}),d.insert((note){x + 1,r});
                update(l,x,l,x,q - i),update(x + 1,r,x + 1,r,q - i);
            }
            a[x] ^= 1;
        }
        else
        {
            scanf("%d",&y);
            set<note>::iterator itl = --d.upper_bound((note){x,0});
            set<note>::iterator itr = --d.upper_bound((note){y,0});
            if(itl == itr)
                printf("%lld\n",query(x,y) - q + i);
            else
                printf("%lld\n",query(x,y));
        }
    }
}

『My guiding star.』

LibreOJ 3146 「APIO2019」路灯