Light OJ 1085 / Segment Tree

/***
 created: 2023-01-05-02.09.28
***/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename U> using ordered_set=tree<U, null_type,less<U>,rb_tree_tag,tree_order_statistics_node_update>;
#define ll long long
#define all(we) we.begin(),we.end()
#define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
#define nl '\n'
const ll mod=1e9+7;

ll tr[500005];

bool cmp(pair<ll,ll>a,pair<ll,ll>b)
{
    if(a.first==b.first) return a.second>b.second;
    return a.first<b.first;
}

void treeconstruct(ll node,ll b,ll e)
{
    if(b==e)
    {
        tr[node]=0;
        return;
    }
    ll left = node*2;
    ll right = left|1ll;
    ll mid=(b+e)/2;
    treeconstruct(left,b,mid);
    treeconstruct(right,mid+1,e);
    tr[node]=tr[left]+tr[right];
}


void update(ll node,ll b,ll e,ll i,ll newv)
{
    if(i>e || i<b) return;
    if(b==e)
    {
        tr[node]=newv;
        return;
    }
    ll left = node*2;
    ll right = left+1;
    ll mid=(b+e)/2;
    update(left,b,mid,i,newv);
    update(right,mid+1,e,i,newv);
    tr[node]=(tr[left]+tr[right])%mod;
}

ll queries(ll node,ll b,ll e,ll i,ll j)
{
    if(i>e || j<b) return 0;
    if(b>=i && e<=j) return tr[node];
    ll left = node*2;
    ll right = left+1;
    ll mid=(b+e)/2;
    ll x=queries(left,b,mid,i,j);
    ll y=queries(right,mid+1,e,i,j);
    return (x+y)%mod;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);


    test
    {
        ll n,m,i,j,k,l;

        cin>>n;

        vector<pair<ll,ll>>x;

        for(i=1;i<=n;i++)
        {
            cin>>m;
            x.push_back({m,i});
        }

        treeconstruct(1,1,n);

        sort(all(x),cmp);

        for(i=0;i<n;i++)
        {
            l=queries(1,1,n,1,x[i].second);
            update(1,1,n,x[i].second,l+1);
        }

        cout<<"Case "<<cs<<": "<<queries(1,1,n,1,n)<<nl;
    }

    return 0;
}