算法练习：差分 区间合并

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

typedef pair<int,int> PII;
vector<PII> segs;
const int N=200010;

void insert(int b[N],int l,int r,int c)
{
    b[l]+=c;
    b[r+1]-=c;
}

void merge(vector<PII> &segs)
{
    vector<PII> res;
    sort(segs.begin(),segs.end());
    int st=-2e9,ed=-2e9;
    for(auto seg:segs)
    {
        if(ed<seg.first)
        {
            if(st!=-2e9) res.push_back({st,ed});
            st=seg.first;
            ed=seg.second;
        }
        else ed=max(ed,seg.second);
    }
    if(st!=-2e9) res.push_back({st,ed});
    segs=res;
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        int a[N];
        int b[N]={0};
        vector<int> vec;
        vector<PII> segs;
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
            vec.push_back(0);
            insert(b,i,i,0);
            if(a[i]==0) continue;
            int l,r;
            r=vec.size()-1;
            if(r-a[i]+1<0) l=0;
            else l=r-a[i]+1;
            segs.push_back({l,r});
        }
        merge(segs);
        for(auto seg:segs)
        {
            insert(b,seg.first,seg.second,1);
        }
        for(int i=0;i<n;i++) b[i]+=b[i-1];
        for(int i=0;i<n;i++) printf("%d ",b[i]);
        printf("\n");
    }
    return 0;
}