题解 | 小红的区间修改（一）

#include<iostream>

using namespace std;

const int N=3e5+5;

int q,n;
int l[N],r[N],tr[N];

inline int lowbit(int x){return x&-x;}

inline void update(int x,int y)
{
    for(int i=x;i<=n;i+=lowbit(i))
        tr[i]+=y;
    return;
}

inline int query(int x)
{
    int res=0;
    while(x)
    {
        res+=tr[x];
        x-=lowbit(x);
    }
    return res;
}

int main()
{
    cin>>q;
    for(int i=1;i<=q;i++) cin>>l[i]>>r[i],n=max(n,r[i]);
    int cnt=1;
    for(int i=1;i<=q;i++)
    {
        int tmp1=query(l[i]),tmp2=query(r[i]);
        if(tmp1!=tmp2)
        {
            cout<<cnt+1<<endl;
        }
        else
        {
            update(l[i],1),update(r[i],1);
            cnt=max(cnt,r[i]-l[i]+1);
            cout<<cnt+1<<endl;
        }
    }
    return 0;
}