【APIO2019】路灯 | Mrsrz's blog

树套树

题目大意：

一条街道有 $n$ 个路灯和 $n+1$ 个位置，每个路灯连接相邻两个位置。两个位置可以通行，必须满足连接两个位置的路灯亮着。

现在有两个操作：

1. 修改一盏灯的状态
2. 给定位置 $a,b$，询问从 $0$ 到当前，有多少个时刻满足 $a$ 到 $b$ 连通。

题解：

考虑将起点为 $a$ 终点为 $b$ 看做二维平面上的点对。

一个区间 $[l,r]$，其中在位置 $x$ 断开，那么 $[l,x]$ 的每个点到 $[x+1,r]$ 的每个点，都由连通变为不连通。我们对每个点对增加 $t-q$，表示断开。

两个区间 $[l,x]$ 和 $[x+1,r]$ 连通，那么 $[l,x]$ 的每个点到 $[x+1,r]$ 的每个点，都由不连通变为连通。我们对每个点对增加 $q-t$。

观察可得，两个点连通了一段连续的时间，这个点对的值恰好增加了它亮着的时间。

那么查询的时候直接单点查询值即可。如果查询的时候这两个点是连通的，要看做这个时刻不连通处理，以正确计算贡献。

这样问题转化为矩阵加、单点查询问题。可以使用树套树来实现。

需要知道一个段的左、右端点，用 set 维护即可。

时间复杂度 $O((n+q)\log^2 n)$。

Code：

#include<iostream>
#include<set>
using namespace std;
const int N=3e5+5,M=3e7;
int n,q,rt[N];
int d[M],ls[M],rs[M],nod=0;
char s[N];
set<pair<int,int> >st;
void add_2d(int&o,int l,int r,const int&pos,const int&val){
    if(!o)o=++nod;
    if(l==r)d[o]+=val;else{
        const int mid=l+r>>1;
        if(pos<=mid)add_2d(ls[o],l,mid,pos,val);else add_2d(rs[o],mid+1,r,pos,val);
        d[o]=d[ls[o]]+d[rs[o]];
    }
}
void add_1d(int l,int r,const int&L,const int&R,const int&val){
    for(int i=l;i<=n;i+=i&-i)add_2d(rt[i],1,n+1,L,val),add_2d(rt[i],1,n+1,R+1,-val);
    for(int i=r+1;i<=n;i+=i&-i)add_2d(rt[i],1,n+1,L,-val),add_2d(rt[i],1,n+1,R+1,val);
}
int ask_2d(int o,int l,int r,const int&L,const int&R){
    if(!o)return 0;
    if(L<=l&&r<=R)return d[o];
    const int mid=l+r>>1;int ret=0;
    if(L<=mid)ret=ask_2d(ls[o],l,mid,L,R);
    if(mid<R)ret+=ask_2d(rs[o],mid+1,r,L,R);
    return ret;
}
int ask_1d(int i,int Pos){
    int ret=0;
    for(;i;i&=i-1)ret+=ask_2d(rt[i],1,n+1,1,Pos);
    return ret;
}
void init(){
    for(auto it:st){
        int l=it.first,r=it.second;
        for(int i=l;i<r;++i)
            add_1d(i,i,i+1,r,q);
    }
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>q;++n;
    int lst=1;
    cin>>(s+1);
    for(int i=1;i<n;++i){
        if(s[i]=='0'){
            st.insert(make_pair(lst,i));
            lst=i+1;
        }
    }
    st.insert(make_pair(lst,n));
    init();
    for(int T=1;T<=q;++T){
        char op[8];
        cin>>op;
        if(*op=='t'){
            int x;
            cin>>x;
            if(s[x]=='0'){
                s[x]='1';
                auto R=st.lower_bound(make_pair(x+1,0));auto L=--R;++R;
                int l=L->first,r=R->second;
                st.erase(L),st.erase(R);
                st.insert(make_pair(l,r));
                add_1d(l,x,x+1,r,q-T);
            }else{
                s[x]='0';
                auto it=--st.lower_bound(make_pair(x,1000000));
                int l=it->first,r=it->second;
                st.erase(it);
                st.insert(make_pair(l,x)),st.insert(make_pair(x+1,r));
                add_1d(l,x,x+1,r,T-q);
            }
        }else{
            int a,b;
            cin>>a>>b;
            int ans=ask_1d(a,b);
            auto it=--st.lower_bound(make_pair(a,1000000));
            if(it->first<=b&&b<=it->second)ans+=T-q;
            cout<<ans<<'\n';
        }
    }
    return 0;
}