acm模式

#include<bits/stdc++.h>
using namespace std;
#define ls (x<<1)
#define rs (x<<1)+1

vector<int> nums;

void input()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        nums.push_back(x);
    }
}

const int maxn=2005;
int a[maxn];
int b[maxn];
int asz=0;
int sz;
int nownum=1;

struct node
{
    int l,r;
    pair<int,int> maxinfo;
    // int maxlen=0;
    // int maxlennum=0;
    int lazy=0;
}tree[maxn<<2];

void seperate()
{
    sz=nums.size();
    for(int i=0;i<sz;i++)
    {
        b[i+1]=nums[i];
    }
    sort(b+1,b+sz+1);
    for(int i=0;i<sz;i++)
    {
        a[i+1]=lower_bound(b+1,b+sz+1,nums[i])-b;

        asz=max(asz,a[i+1]);
    }
}
void outpair(pair<int,int> p)
{
    cout<<p.first<<" "<<p.second<<endl;
}
pair<int,int> join(pair<int,int> p1,pair<int,int> p2)
{

    int v1=p1.first;
    int n1=p1.second;
    int v2=p2.first;
    int n2=p2.second;
    // if(v1==0) return p2;
    // if(v2==0) return p1;
    pair<int,int> info;
    if(v1==v2)
    {
        info.first=v1;
        info.second=n1+n2;
    }
    else if(v1>v2)
    {
        info.first=v1;
        info.second=n1;     
    }
    else
    {
        info.first=v2;
        info.second=n2;        
    }
    return info;
}

void build(int l,int r,int x)
{
    if(l>r)
    {
        return;
    }
    tree[x].l=l;
    tree[x].r=r;
    if(l==r)
    {
        // tree[x].maxinfo.first=1;
        // tree[x].maxinfo.second=acnt[a[l]];
        //tree[x].maxinfo.second+=1;
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,ls);
    build(mid+1,r,rs);
    pair<int,int> p1(0,0),p2(0,0);
    p1=tree[ls].maxinfo;
    p2=tree[rs].maxinfo;
    tree[x].maxinfo=join(p1,p2);
}

pair<int,int> query(int bl,int br,int l,int r,int x)
{
    
    if(l>r)
    {
        return pair<int,int>(0,1);
    }
    if(l>br||r<bl)
    {
        return pair<int,int>(0,1);
    }
    pair<int,int> p1(0,1),p2(0,1);
     int mid=(l+r)>>1;
     pair<int,int> p;
    if(l>=bl&&r<=br)
    {
        if(l==r)
        {
            return tree[x].maxinfo;
        }
        if(tree[x].lazy)
        {
            p1=query(bl,br,l,mid,ls);
            p2=query(bl,br,mid+1,r,rs);
            tree[x].lazy=0;
        }
        else
        {
            p1=tree[ls].maxinfo;
            p2=tree[rs].maxinfo;
        }
        // cout<<"l r "<<l<<" "<<r<<endl;
         p=join(p1,p2);
        // outpair(p1);
        // outpair(p2);
        // outpair(p);
        // cout<<"\\n";
        tree[x].maxinfo=p;
    }
    else
    {
        if(bl<=mid)
        {
            p1=query(bl,br,l,mid,ls);
        }
        if(br>mid)
        {
            p2=query(bl,br,mid+1,r,rs);
        }
        p=join(p1,p2);
    }

    return p;

}
void change(int l,int r,int x,int target,int val)
{
    if(l>r)
    {
        return;
    }
    if(l<=target&&r>=target)
    {
        if(l==r)
        {
            if(val==tree[x].maxinfo.first)
            {
                tree[x].maxinfo.second+=nownum;
            }
            else
            {
                tree[x].maxinfo.first=val;
                tree[x].maxinfo.second=nownum;
            }
            // cout<<"change res\\n"<<l<<"\\n";
            // outpair(tree[x].maxinfo);
            
            return;
        }
        int mid=(l+r)>>1;
        tree[x].lazy=1;
        change(l,mid,ls,target,val);
        change(mid+1,r,rs,target,val);
    }

}
void outputa()
{
    for(int i=1;i<=sz;i++)
    {
        cout<<a[i]<<" ";
    }
    cout<<endl;
}
void outputtree()
{
    cout<<"------check tree---------\\n";
    for(int i=1;i<=sz*4;i++)
    {
        cout<<"i="<<i<<" "<<tree[i].l<<" "<<tree[i].r<<endl;
        cout<<tree[i].maxinfo.first<<endl;
        cout<<tree[i].maxinfo.second<<endl;
    }
    cout<<"------check tree---------\\n";
}
void init()
{
    for(int i=0;i<maxn;i++)
    {
        a[i]=0;b[i]=0;
    }
    asz=0;
    sz=0;
    nownum=1;
}
int solve()
{
    //lc
    //
    int ans=1;
    init();
    seperate();
 //  outputa();
    build(1,asz,1);
   // outputtree();

    int maxlennum=1;
    pair<int,int> info;
    for(int id=1;id<=sz;id++)// 每个数
    {
        int num=a[id];
      //  nownum=1;
 //    cout<<"\\nnum"<<num<<endl;
        info=query(1,num-1,1,asz,1);
        if(info.first==0) info.second=1;
 //outputtree();
    // outpair(info);
       
        int len=info.first;
        len++;
        nownum=info.second;
     //   cout<<"len "<<len<<endl;
        change(1,asz,1,num,len);//1 2 1 2 1
      //  outputtree();
    }
    info=query(1,asz,1,asz,1);
  //  outputtree();
   // outpair(info);
    ans=info.second;
    return ans;
}
signed main()
{
    input();
    cout<<solve();
    return 0;
}

//如果前面检测0 那就只有一种情况是不选
//

关键代码模式