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

#include <bits/stdc++.h>
#include <iostream>
using namespace std;
typedef long long ll;
const int N = 3e5+10;
int a[N];
int tree[N];
int lowbit(int x)
{
    return x&-x;
}

void add(int x,int v)
{
    
    while(x<=N-10)
    {
        tree[x]+=v;
        x += lowbit(x);

    }
}


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




int main()
{
    int q;
    cin>>q;
    int ans = 1;
    int cnt = 0;
    while(q--)
    {
        int l,r;
        cin>>l>>r;
        int sum = query(r)-query(l-1);
        if(sum==0)
        {
            for(int i=l;i<=r;i++)
            {
                add(i,i-l+1);
                cnt += r-l+1;
            }
            if(cnt!=N-10)ans = max(r-l+2,ans);
            else ans = max(r-l+1,ans);
        }
        cout<<ans<<endl;
    }
    return 0;
}

题解应该没人用树状数组罢，直接使用树状数组查询区间累加和，为0则暴力修改，否则就跳过，直接输出当前最大值